[실버 1] 백준 1926 - 그림 (파이썬)

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

풀이

도화지에는 0 또는 1로 된 값이 채워진 N * M 크기의 이차원 배열이 있다.

1은 그림의 일부, 0은 빈 공간.

그림은 상하좌우로 연결된 1들의 집합이며, 그림의 개수와 가장 넓은 그림의 넓이를 출력해야한다.

즉, BFS로 1을 시작점으로 탐색하여 그림 하나를 모두 탐색하고, 이미 방문한 좌표는 visit 배열로 체크한다,

각 BFS마다 count로 넓이를 측정한다.

queue = deque()
visit = [[False] * M for _ in range(N)]

BFS용 큐를 초기화 하고, visit은 해당 좌표를 이미 방문했는지 여부를 저장하는 2차원 리스트이다.

dr = [0, 0, 1, -1]
dc = [-1, 1, 0, 0]

상, 하, 좌, 우 방향 이동을 위한 배열이며, (r, c)에서 (r + dr[k], c + dc[k])로 이동할 수 있도록 구성한다.

for i in range(N):
    for j in range(M):
        if B[i][j] == 1 and not visit[i][j]:

전체 좌표를 탐색하면서, 아직 방문하지 않은 1을 찾고, 이게 곧 새로운 그림의 시작점이라는 뜻이다.

queue.append((i, j))
visit[i][j] = True
count = 1

BFS로 그림을 탐색하기 위해서 그림 시작 좌표를 큐에 넣고 방문처리하고, 이 그림의 넓이를 셀 변수 count를 1로 초기화한다.

while len(queue) != 0:
    r, c = queue.popleft()

BFS를 시작하여, 큐가 빌때까지 반복하며, 현재 위치 (r, c)를 꺼내어 연결된 1을 탐색한다.

for k in range(4):
    nr, nc = r + dr[k], c + dc[k]
    if nr < 0 or N <= nr or nc < 0 or M <= nc:
        continue

다음 좌표 (nr, nc)로 이동하고, 도화지를 벗어나는 경우는 continue 처리한다.

if B[nr][nc] == 1 and not visit[nr][nc]:
    queue.append((nr, nc))
    visit[nr][nc] = True
    count += 1

인접한 좌표가 1이고 아직 방문하지 않았다면, 큐에 넣고 방문처리하고, 넓이를 증가한다.

시간 복잡도 분석

전체 탐색은 O(NM), 각 칸은 최대 한번만 방문하므로 효육적임

코드

# 백준 1926 - 그림
# 분류 : BFS

from collections import deque

N, M = map(int, input().split())
B = [list(map(int, input().split())) for _ in range(N)]

queue = deque()
visit = [[False] * M for _ in range(N)]

dr = [0, 0, 1, -1]
dc = [-1, 1, 0, 0]

num_pictures = 0
max_count = 0
for i in range(N) :
    for j in range(M) :
        if B[i][j] == 1 and not visit[i][j] :
            queue.append((i, j))
            visit[i][j] = True
            count = 1
            while len(queue) != 0 :
                r, c = queue.popleft()

                for k in range(4) :
                    nr, nc = r + dr[k], c + dc[k]
                    if nr < 0 or N <= nr or nc < 0 or M <= nc :
                        continue
                    if B[nr][nc] == 1 and not visit[nr][nc] :
                        queue.append((nr, nc))
                        visit[nr][nc] = True
                        count += 1
            max_count = max(max_count, count)
            num_pictures += 1

print(num_pictures)
print(max_count)