[백준] 1976 - 그림 (Python)

문제 설명

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

1926번: 그림

---

문제 풀이

visited로 방문 여부를 기록하였고,

이중 포문으로 값이 1이면서 아직 방문하지 않은 지점일 때 bfs를 시작하여 bfs의 시작점을 구했다.

가장 넓은 그림의 넓이를 출력하기 위해 max를 사용하여 비교했다!

 

from collections import deque

n, m = map(int, input().split())
visited = [[False] * m for _ in range(n)]
draw = [list(map(int, input().split())) for _ in range(n)]

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def bfs(x, y):
    size = 1
    queue = deque()
    queue.append((x, y))
    visited[x][y] = True

    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue
            if draw[nx][ny] == 0 or visited[nx][ny]:
                continue
            queue.append((nx, ny))
            visited[nx][ny] = True
            size += 1
    return size

result = 0
max_size = 0
for i in range(n):
    for j in range(m):
        if draw[i][j] == 1 and not visited[i][j]:
            result += 1
            max_size = max(max_size, bfs(i, j))

print(result)
print(max_size)