[백준 알고리즘] 1926번: 그림 (Python / 파이썬)

문제 접근

bfs로 이차원 배열을 탐색해야 한다.

1) 이차원 배열을 차례대로 순회하면서, 1이 등장할 때마다 bfs를 호출한다.

2) bfs를 진행하면서 해당 영역의 그림 칸 수를 카운트함과 동시에 바로 0으로 바꿔준다.

3) bfs에서 반환된 카운트 값을 가지고 max와 비교해 업데이트

4) 2)에서 방문한 부분은 0으로 바꿔줬기 때문에 1)에서는 또다른 영역의 그림만을 인식하여 bfs를 호출하게 된다.

 

정답 코드

#1926번: 그림

import sys
from collections import deque

def bfs(map, x, y):
    queue = deque()
    queue.append((x, y))
    map[x][y] = 0
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    count = 0

    while queue:
        cur = queue.popleft()
        count += 1
        for i in range(4):
            nx, ny = cur[0] + dx[i], cur[1] + dy[i]
            if nx >= 0 and nx < n and ny >= 0 and ny < m:
                if map[nx][ny] == 1:
                    queue.append((nx, ny))
                    map[nx][ny] = 0
    return count


n, m = map(int, sys.stdin.readline().split())
map = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
max = 0
count = 0

for i in range(n):
    for j in range(m):
        if map[i][j] == 1:
            count += 1
            temp = bfs(map, i, j)
            if temp > max:
                max = temp

print(count)
print(max)

---

1926번: 그림