백준 1926 그림 (파이썬)

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

1926번: 그림

전형적인 bfs문제입니다.

bfs 시행 횟수를 res 리스트에 저장하여 최댓값을 출력합니다.

res에 결괏값이 없을 시 0을 출력해줍니다

 

from collections import deque
 
 
def bfs(x, y):
    cnt = 1
    dq = deque()
    dq.append([x, y])
    visit[x][y] = True
    while dq:
        x, y = dq.popleft()
        for dx, dy in direction:
            nx, ny = x + dx, y + dy
            if 0 <= nx < N and 0 <= ny < M and paint[nx][ny] == 1 and not visit[nx][ny]:
                dq.append([nx, ny])
                visit[nx][ny] = True
                cnt += 1
    res.append(cnt)
 
 
N, M = map(int, input().split())
paint, res = [], []
direction = [(0, 1), (1, 0), (0, -1), (-1, 0)]
visit = [[False for _ in range(M)] for _ in range(N)]
for i in range(N):
    paint.append(list(map(int, input().split())))
for i in range(N):
    for j in range(M):
        if paint[i][j] == 1 and not visit[i][j]:
            bfs(i, j)
if res:
    print(len(res))
    print(max(res))
else:
    print(0)
    print(0)