[백준][1012] 유기농 배추

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

문제

• 배추가 위치한 곳은 "1", 배추가 위치하지 않은 곳은 "0"으로 표시
• 배추흰지렁이는 인접한 배추로만 이동 가능
• 필요한 최소한의 배추흰지렁이의 수 구하기

입력

• 테스트 케이스 T
• 배추밭의 가로길이 M, 세로길이 N, 배추가 심어져 있는 위치의 개수 K
• 배추의 위치 X, Y

출력

• 각 테스트 케이스에 대해 필요한 최소의 배추흰지렁이 마리 수

풀이

이 문제를 처음보고 바로 떠오른 것은 DFS 방식이다.

1. 배추가 위치한 곳에 도착하면 상하좌우를 재귀함수로 방문한다.
2. 방문한 배추의 위치를 0으로 변경한다.
3. 방문할 수 있는 배추의 위치를 모두 방문 완료 시 COUNT값을 1 증가시키다.
3. 배열의 끝에 도착 시 COUNT 저장한다.
4. 위 1-4번 과정을 테스트 케이스 T만큼 반복한다.
5. COUNT 출력

재귀 함수 부분을 다음과 같이 구현

def dfs(y1, x1, ground, m, n):
   ground[y1][x1] = 0

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

   for i in range(4):
       y2 = y1 + dy[i]
       x2 = x1 + dx[i]
       if y2 < 0 or m <= y2 or x2 < 0 or n <= x2:
           continue

       if ground[y2][x2] == 1:
           dfs(y2, x2, ground, m, n)

• 이동할 좌표를 y2, x2라고 설정한 후 해당 좌표가 배열의 범위를 벗어나지 않는지 확인 후 벗어날 경우 배추 여부를 확인하지 않는다.
• 이동할 좌표가 배열의 범위를 벗어나지 않을 경우 배추 여부를 확인해서 배추가 심어져 있는 위치일 경우 해당 위치에 방문한다.

오류 및 해결

• Recursion Error가 발생했다. Recursion이 너무 깊어질 경우 발생하는 파이썬 오류이다.
• 다음과 같이 코드를 작성해 DFS를 재귀로 푸는 경우 최대 재귀 횟수 제한을 풀어줄 수 있다.

import sys

sys.setrecursionlimit(10**5)

코드

import sys

sys.setrecursionlimit(10**5)


def dfs(y1, x1, ground, m, n):
    ground[y1][x1] = 0

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

    for i in range(4):
        y2 = y1 + dy[i]
        x2 = x1 + dx[i]
        if y2 < 0 or m <= y2 or x2 < 0 or n <= x2:
            continue

        if ground[y2][x2] == 1:
            dfs(y2, x2, ground, m, n)


for _ in range(int(input())):
    ans = 0

    arr = []
    m, n, k = map(int, input().split())
    ground = [[0 for _ in range(n)] for __ in range(m)]
    for _ in range(k):
        x, y = map(int, input().split())
        ground[x][y] = 1
        arr.append([x, y])

    for i in range(k):
        arr[i].reverse()

    for x, y in arr:
        if ground[y][x] == 1:
            dfs(y, x, ground, m, n)
            ans += 1

    print(ans)