[Boj] 그림 1926(python)

문제링크 : https://www.acmicpc.net/problem/1926

구해야 할 목적이 그림의 갯수와 가장 큰 그림이므로, DFS와 BFS 모두 가능하나 필자는 BFS를 선택함

그림이 그려져 있는 곳에서 BFS 함수 실행, 가야할 곳을 큐로 관리

BFS 함수를 실행하여 좌표를 하나씩 꺼내서 상하좌우 검사 후 조건에 맞는 좌표를 큐에 넣음

검사한 곳은 0으로 만들어주고, area에 1씩 더해나감

from collections import deque
import sys

def BFS(row, col):
    area = 1
    to_visits = deque()
    to_visits.append([row, col])
    metrix[row][col] = 0
    while to_visits:
        current_row, current_col = to_visits.popleft()
        for idx in range(4):
            next_row = current_row + dx[idx]
            next_col = current_col + dy[idx]
            if 0 <= next_row < n and 0 <= next_col < m and metrix[next_row][next_col]:
                to_visits.append([next_row, next_col])
                metrix[next_row][next_col] = 0
                area += 1
    return area

metrix = []
n, m = map(int, input().split())
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
for _ in range(n):
    tmp = list(map(int, input().split()))
    metrix.append(tmp)

cnt = 0
answer = 0
for row in range(n):
    for col in range(m):

        if metrix[row][col]:
            cnt += 1
            picture = BFS(row, col)
            if picture > answer:
                answer = picture

print(cnt)

print(answer)