[PS] BFS: 1012 유기농 배추

문제 출처

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

포인트

DFS시 깊이가 깊어져서 RecursionError발생하는 문제가 생겼습니다.
BFS를 통해 재귀함수 호출 없이 탐색을 하여 해결

코드

import sys
from collections import deque

input = sys.stdin.readline


def bfs(x, y, graph, width, height):
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    queue = deque([(x, y)])
    graph[y][x] = 0
    while queue:
        x, y = queue.popleft()

        for dx, dy in directions:
            nx, ny = x + dx, y + dy

            if 0 <= nx < width and 0 <= ny < height and graph[ny][nx] == 1:
                graph[ny][nx] = 0
                queue.append((nx, ny))


def solve():
    test_case_cnt = int(input().strip())

    for _ in range(test_case_cnt):
        M, N, K = map(int, input().split())
        graph = [[0] * M for _ in range(N)]

        for _ in range(K):
            x, y = map(int, input().split())
            graph[y][x] = 1

        worm_count = 0
        for y in range(N):
            for x in range(M):
                if graph[y][x] == 1:
                    bfs(x, y, graph, M, N)
                    worm_count += 1
        print(worm_count)


if __name__ == "__main__":
    solve()

코멘트

파이참에서 테스트 해보면 잘 되는데 제출하면 에러가 나서 당황했다..