BOJ 1926. 그림 (Python)

문제

BOJ 1926

내가 생각한 풀이

이중 for문을 돌며 방문하지 않았으면서 1인 지점에 BFS를 수행한다.

BFS를 수행한 횟수가 그림의 갯수가 되며 BFS는 그림의 넓이를 리턴하도록 한다.

리턴된 그림의 넓이와 그림의 최대 넓이를 비교하며 그림의 최대 넓이를 구한다.

 

코드 (Python)

import sys
from collections import deque
input = sys.stdin.readline

N, M = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(N)]
visited = [[False] * M for _ in range(N)]
direction = [(-1, 0), (1, 0), (0, -1), (0, 1)]


def bfs(graph, x, y, visited) -> int:
    queue = deque([(x, y)])
    visited[x][y] = True
    area = 1
    while queue:
        xp, yp = queue.popleft()
        for dx, dy in direction:
            nx, ny = xp + dx, yp + dy
            if not (0 <= nx < N and 0 <= ny < M):
                continue
            if not visited[nx][ny] and graph[nx][ny] == 1:
                queue.append((nx, ny))
                visited[nx][ny] = True
                area += 1
    return area


cnt = 0
mx = 0
for i in range(N):
    for j in range(M):
        if graph[i][j] == 1 and not visited[i][j]:
            cnt += 1
            area = bfs(graph, i, j, visited)
            mx = max(mx, area)
print(cnt)
print(mx)