백준 - 그림 1926 (Python)

[Silver I] 그림 - 1926
https://www.acmicpc.net/problem/1926

 

문제설명

어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로로 연결된 것은 연결이 된 것이고 대각선으로 연결이 된 것은 떨어진 그림이다. 그림의 넓이란 그림에 포함된 1의 개수이다.

 

입력

첫째 줄에 도화지의 세로 크기 n(1 ≤ n ≤ 500)과 가로 크기 m(1 ≤ m ≤ 500)이 차례로 주어진다. 두 번째 줄부터 n+1 줄 까지 그림의 정보가 주어진다. (단 그림의 정보는 0과 1이 공백을 두고 주어지며, 0은 색칠이 안된 부분, 1은 색칠이 된 부분을 의미한다)

 

출력

첫째 줄에는 그림의 개수, 둘째 줄에는 그 중 가장 넓은 그림의 넓이를 출력하여라. 단, 그림이 하나도 없는 경우에는 가장 넓은 그림의 넓이는 0이다.

 

 

예제입력 / 예제출력

 

문제이해 및 코드설명

문제는 수가 주어지는데 1은 연결된 그림 0은 연결되지 않은 그림일 때 몇개의 그림이 생기고 최대그림의 크기는 얼마인지를 구하는 문제이다. 이 문제는 bfs를 통해 그래프를 탐색하며 풀어보았다.

우선 bfs를 풀 때는 선입선출이 가능한 deque을 사용한다 (popleft사용)

수들을 입력 받고 입력받은 배열을 graph형태로 만들어준다.

이후 상하 좌우 탐색을위해 임의의 변수 dx, dy를 만들어준후 1이 생긴 곳에 bfs 함수를 실행시켜주는 방식이다.

bfs함수는 우선 queue에 배열의 위치값을 넣어준 후 개수를 세어준다. 이 후 방문 처리한 곳은 재방문하는 사태를 방지하기 위해 0으로 바꿔준 후 queue에서 가장 오래된 값을 제거해준다.다음 상하좌우를 살피며 1이 있는 지 확인하고 1이 있다면 queue에 추가하고 graph에 값을 0 으로 바꿔주는 코드를 실행한다. paint는 임의의 변수로 각 그림의 크기가 몇개인지 cnt해준 값이 입력이 되는 방식이다.  

 

 

 

코드

import sys
from collections import deque


n, m = map(int, sys.stdin.readline().split())
graph = []
for i in range(n):
    graph.append(list(map(int,sys.stdin.readline().split())))

dx = [0,0,1,-1]
dy = [1,-1,0,0]

def bfs(graph,a,b):
    queue = deque()
    queue.append((a,b))
    graph[a][b]=0
    cnt = 1

    while queue:
        x,y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >=n or ny < 0 or ny >= m:
                continue
            if graph[nx][ny] == 1:
                graph[nx][ny] = 0
                queue.append((nx,ny))
                cnt += 1
    return cnt
paint = []

for i in range(n):
    for j in range(m):
        if graph[i][j] == 1:
            paint.append(bfs(graph,i,j))

if len(paint)==0:
    print(len(paint))
    print(0)
else:
    print(len(paint))
    print(max(paint))