[BOJ/Python] 1926_그림

문제 출처:https://www.acmicpc.net/problem/1926

1926번: 그림

 

문제

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

입력

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

출력

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

예제 입력 1

6 5
1 1 0 1 1
0 1 1 0 0
0 0 0 0 0
1 0 1 1 1
0 0 1 1 1
0 0 1 1 1

예제 출력 1

4
9

---

풀이

 

그림의 개수를 구하고, 구한 그림들 중 가장 넓은 면적을 출력하는 문제이다.

BFS를 이용하여 풀었다. 코드는 다음과 같다.

 

import sys
import collections
 
dx = [-1,0,1,0]
dy = [0,-1,0,1]
grid = []
 
count = 0
area = 0
 
def bfs(x,y):
    area = 0
    queue = collections.deque()
    queue.append((x,y))
    grid[x][y]='0'
    while queue:
        x,y = queue.popleft()
        area +=1
        for i in range(4):
            px = x + dx[i]
            py = y + dy[i]
            if 0<=px<n and 0<=py<m:
                if grid[px][py]=='1':
                    grid[px][py]='0'
                    queue.append((px,py))
 
    return area
 
 
n,m = map(int,sys.stdin.readline().split())
for _ in range(n):
    grid.append(list(sys.stdin.readline().split()))
 
for i in range(n):
    for j in range(m):
        if grid[i][j]=='1':
            count+=1
            area = max(area,bfs(i,j))
 
print(count)
print(area)

 

• dx와 dy는 좌표를 상,하,좌,우 이동하여 살펴보기 위해 생성하였다.
• 우선 이중 for문을 이용하여 주어진 그림의 정보를 탐색한다.
• 여기서 현재 탐색하고 있는 좌표의 값이  '1'이라면 그림이므로, 우선 그림의 개수인 count를 1 증가시킨다.
• 그리고 현재 좌표를 기준으로 bfs를 수행한다. 함수 bfs에 대한 설명은 다음과 같다.
• bfs는 큐를 이용하여 구현하며, 우선 현재 좌표의 값을 '0'으로 바꾸어 방문 처리한다.
• while문은 큐에 데이터가 있을 때 동안 반복한다.
• 현재 좌표를 기준으로 상하좌우를 살피고, 만약 '1'이 있다면 현재 그림과 연결되어 있는 부분이므로 우선 '0'으로 바꾸어 방문처리를 해주고, 그 좌표를 큐에 추가한다.
• 그러면 그 좌표를 기준으로 또 상하좌우 살피게 되고, 연결되어 있는 부분이 존재하는지 확인하게 된다.
• 만약 큐가 비었다면, 더 이상 연결되어 있는 부분이 없다는 의미로 area를 return 한다.
• area의 경우, 큐가 popleft를 할 때마다 1씩 증가시킨다. (큐에 들어간 원소의 개수가 곧 그림의 면적이기 때문이다.)
• 현재 그림의 면적이 최대인지 비교하며, 최종적으로 최댓값을 구한다.