[Algorithm] 백준 1012 유기농 배추 | 파이썬 BFS

※ 1012 유기농 배추

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

문제 해결 TIP

처음에 DFS로 풀다가 RecursionError에 걸려서 BFS로 바꾸었다. 바이러스 문제와 비슷하게 상하좌우 주변 노드들을 방문하며 큐에 삽입하고 탐색하는 방법으로 진행한다. 여기서 주의할 점은 문제에서 가로 길이를 M, 세로 길이를 N으로 주어진 점이다.

 

전체 코드

from collections import deque

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

def bfs(x, y):
    queue = deque()
    queue.append((x, y))
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or ny < 0 or nx >= M or ny >= N:
                continue
            if graph[nx][ny] == 1:
                queue.append((nx, ny))
                graph[nx][ny] = 0

T = int(input())
for _ in range(T):
    count = 0
    M, N, K = map(int,input().split())
    graph = [[0 for _ in range(N)] for _ in range(M)]
    for _ in range(K):
        i,j = map(int,input().split())
        graph[i][j] = 1
    #graph = [[1, 0, 0, 0, 0, 0, 0, 0], [1, 1, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 1, 0, 0, 0], [0, 0, 0, 0, 1, 0, 0, 0], [0, 0, 1, 1, 0, 1, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 1, 1, 1, 0], [0, 0, 0, 0, 1, 1, 1, 0], [0, 0, 0, 0, 1, 1, 1, 0]]

    for i in range(M):
        for j in range(N):
            if graph[i][j] == 1:
                bfs(i,j)
                count += 1
    print(count)