백준 1743번-BFS solution (Python)

BFS 연습용 문제 - 인접한 노드가 가장 많은 부분 크기 찾기

풀이

from collections import deque

N, M, K = map(int, input().split())
matrix = [[0] * M for _ in range(N)]
visited = [[0] * M for _ in range(N)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

for _ in range(K):
    x, y = map(int, input().split())
    matrix[x-1][y-1] = 1

def BFS():
    q.append((i, j))
    t = 1
    visited[i][j] = 1
    while q:
        x, y = q.popleft()                
        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]
            if (0<=nx<N) and (0<=ny<M):
                if visited[nx][ny] == 0 and matrix[nx][ny] == 1:
                    visited[nx][ny] = 1
                    q.append((nx, ny))
                    t += 1
    return t

q = deque()
ans = 0
for i in range(N):    
    for j in range(M):
        if matrix[i][j] == 1 and visited[i][j] == 0:
            res= BFS()
            if res > ans: ans = res

print(ans)

문제 출처 백준1743번