BOJ1012 유기농 배추
실버II | 백준 1012 | Python3 파이썬 풀이
BFS 응용 문제이다. 원래는 분리집합(Union&Find)를 이용하는 문제인가 싶었는데, 단순한 탐색 문제였다.
백준의 그래프 탐색 활용 문제 중 가장 기본적인 구조이다.
방문하지 않는 배추에 대해 BFS 탐색을 실시하며 방문했다고 표시한다. 그 그룹의 개수(BFS를 탐색을 시작한 곳의 개수)가 정답이다.
원래는 방문 여부 배열을 따로 만들어서 하는 것이 정석이지만, 이 문제는 한 번 방문한 배추를 다시 방문할 필요가 없으므로 직접 배추밭 배열에서 탐색한 배추(1)를 지워(0으로 변경)버리는 방식으로 탐색했다.
import sys
from collections import deque
move = [[1, 0], [0, 1], [-1, 0], [0, -1]]
def BFS(x, y):
queue = list()
queue.append([x, y])
# BFS
while queue:
n, m = queue[0][0], queue[0][1]
del queue[0]
for ii in range(4):
# 상, 하, 좌, 우로 이동
xx = n + move[ii][0]
yy = m + move[ii][1]
# 맵을 나가지 않고, 배추라면
if 0 <= xx < N and 0 <= yy < M and table[xx][yy] == 1:
# 방문 체크
table[xx][yy] = 0
# 자식 노드 탐색
queue.append([xx, yy])
T = int(sys.stdin.readline())
for t in range(T):
N, M, K = map(int, sys.stdin.readline().split())
table = [[0 for i in range(M)] for j in range(N)]
count = 0
# 배추밭
for k in range(K):
x, y = map(int, sys.stdin.readline().split())
table[x][y] = 1
# 모든 배추에 대해 탐색
for x in range(N):
for y in range(M):
if table[x][y] == 1:
# BFS 탐색
BFS(x, y)
table[x][y] = 0
# 그룹 개수 +1
count += 1
print(count)