[백준 파이썬 1926] 그림

https://www.acmicpc.net/problem/1926

1926번: 그림

 

from collections import deque
import sys

n, m = map(int, input().split())

arr = deque() # 도화지 좌표 
q = deque() # bfs에 쓸 큐 
draw_num = 0 # 그림 개수 
max_area = 0 # 최대 그림 넓이, 그림이 하나도 없는 경우에 가장 넓은 그림의 넓이는 0 이므로 

for _ in range(n):
    arr.append(list(map(int, input().split())))

dx = (0, 0, -1, 1)
dy = (-1, 1, 0, 0)

def bfs(ox, oy):
    seq = 1 # 그림 넓이를 구하기 위한 변수 
    q.append((ox, oy))
    arr[ox][oy] = 0
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if (0<=nx<n) and (0<=ny<m) and (arr[nx][ny] == 1):
                q.append((nx, ny))
                arr[nx][ny] = 0
                seq += 1
    return seq

for i in range(n):
    for j in range(m):
        if arr[i][j] == 1:
            draw_num += 1 # 그림 개수 1개 올림 
            bfs_area = bfs(i, j) # bfs로 구한 그림의 넓이를 저장 
            max_area = max(bfs_area, max_area) # 지금까지 가장 넓은 그림 넓이와 현재 넓이 비교 

print(draw_num) # 그림 개수 출력 
print(max_area) # 최대 그림 넓이 출력

 

드디어 처음으로 구글링 없이 풀었다..! BFS는 이제 그래도 어느정도 감이 온다. 

 

먼저 arr 에 도화지의 좌표값을 받아주었고, 밑의 이중 for 문으로 도화지를 순차적으로 돌면서 좌표값이 1인 좌표(그림의 시작점)을 발견하면 일단 그림을 발견했으니 그림 개수를 +1 해주고, bfs를 현재 좌표를 넣어서 돌려준다. 그리고 bfs의 출력으로 그림의 넓이를 반환하도록 했는데, 이렇게 받은 현재 그림 넓이와 지금까지 그림 넓이 중 가장 큰 값과 비교하여 큰 값을 따로 저장해둔다. 그림이 한 개도 없으면 최대 그림 넓이는 0이라고 했으니 max_area는 0으로 초기화 해주었다. 

 

bfs 에서는 그림 넓이를 구하기 위해 seq 변수에 1부터 시작해서 이웃한 좌표가 1일 경우(그림이 이어지는 경우) +1을 해주고 이때의 이웃한 좌표의 값을 1에서 0으로 변경하여 중복 서칭을 막고, 이 좌표를 큐에 넣어서 또 주위의 이어지는 그림을 찾도록 했다. 그림이 이어지는 좌표가 없으면 최종적으로 seq(그림 넓이)를 반환한다. 

 

도화지를 다 돌면 그림 개수와 최대 그림 넓이를 출력하는 간단한 문제다.