[탐색/BFS] 백준 1012 유기농 배추 - Python

 

[ Contents ]

 

 

1. 문제 (링크 참조)

1012번: 유기농 배추

 

 

 

2. 문제 풀이

 인접한 유기농 배추의 연결 요소 개수를 세는 문제입니다.

 

2022.02.23 - [Algorithm] - [Algorithm] 너비 우선 탐색(BFS), 가까운 주변부터 찾자

[Algorithm] 너비 우선 탐색(BFS), 가까운 주변부터 찾자

 DFS, BFS 모두 가능하며 BFS방식으로 풀이했습니다.

 

 

 

3. 코드

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

#bfs 탐색(탐색할 그래프, 시작지점(x,y))
def bfs(graph, x, y):
    queue = deque()
    queue.append((x, y))
    graph[x][y] = False #시작지점 방문

    direction = [[0,1], [0,-1], [1,0], [-1,0]] #상하좌우 이동
    while queue:
        a, b = queue.popleft()

        #상하좌우 탐색
        for i in range(4):
            dx = a + direction[i][0]
            dy = b + direction[i][1]

            #인접행렬 범위를 벗어나지 않을 때, 배추가 있는지 탐색
            if not (dx < 0 or dy < 0 or dx >= M or dy >= N):
                if graph[dx][dy]:
                    graph[dx][dy] = False
                    queue.append((dx, dy))

 bfs 방식으로 인접행렬을 탐색합니다. 배추가 있을 시, 상하좌우에 또 다른 배추가 있는지 탐색합니다.

 

T = int(input())
for _ in range(T):
    M, N, K = map(int, input().split()) #배추밭의 가로, 세로, 배추 개수
    graph = [[False]*N for _ in range(M)]
    for i in range(K):
        x, y = map(int, input().split())
        graph[x][y] = True #배추 있음

    cnt = 0 #배추 흰 지렁이 개수
    for i in range(M):
        for j in range(N):
            if graph[i][j]: #배추가 있으면
                bfs(graph, i, j) #bfs 시행
                cnt += 1
    print(cnt)

 배추를 표시한 인접행렬의 (0,0)에서 (M,N)까지 차례차례 탐색하며, 배추가 있을 시에 BFS 탐색을 시행합니다.

 BFS탐색을 시행하면 주변 배추들까지 탐색되므로, BFS탐색 횟수가 연결 요소 개수입니다. (배추 흰 지렁이 필요 수)