BaekJoon - 1012번: 유기농 배추 (그래프, 탐색)

DFS 문제를 통해 여러 시행착오를 거칠 필요가 있다고 생각했던 나는 한 문제를 더 찾아서 풀기 시작했고,

재귀 함수를 이용했기에 발생했던 런타임 에러가 발생했다

해결법도 찾았고, 그 방법까지 해서 이번 글에 포스팅하려고 한다

---

문제

1012번: 유기농 배추

 

---

문제 분석

이 문제는 DFS를 이용하여 블록단위 탐색을 이용하면 되지만 몇 가지 유의사항이 존재한다

1. 그래프 형태로 존재하는 것이 아닌 좌표단위로 존재하는 것 -> 가상의 그래프 맵을 만든다
2. 배추밭이 굉장히 넓어졌을 때 재귀를 이용할 경우 깊이의 한계에 막히는 것 -> sys를 import해서 이를 방지한다

---

코드 작성

# Python 자체의 최대 재귀 깊이가 달라질 수 있기에 1000회가 넘을 것으로 예상되면
# sys.setrecursionlimit(10**6)으로 10억회를 설정해서 recursion error을 피하도록 하자
import sys
sys.setrecursionlimit(10**6)

# 테스트 케이스 개수
T = int(input())

# 재귀를 이용한 상하좌우 DFS 블록탐색 함수


def dfs(xpos, ypos):
    if xpos >= N or xpos <= -1 or ypos >= M or ypos <= -1:
        return False

    if d[xpos][ypos] == 1:
        d[xpos][ypos] = 0
        dfs(xpos + 1, ypos)
        dfs(xpos - 1, ypos)
        dfs(xpos, ypos + 1)
        dfs(xpos, ypos - 1)
        return True

    return False


# 테스트 케이스 만큼 반복
for _ in range(T):
    M, N, K = map(int, input().split())
    d = [[0] * M for _ in range(N)]
    for i in range(K):
        # 여기서 주의할 점: y, x의 형태로 심어지므로 좌표값을 변경할 때 주의하자
        x, y = map(int, input().split())
        d[y][x] = 1
    result = 0
    # 2중 반복문으로 블록 개수 탐색
    for i in range(N):
        for j in range(M):
            if dfs(i, j) == True:
                result += 1
    print(result)

RuntimeError : recursion Error 이 발생하는 이유는 Python 자체에서 재귀함수의 재귀 깊이를 막아놓았기 때문인데,

Python에서는 10억회를 무한에 가까운 수로 지정하고 있기에

sys를 불러와서 setrecursionlimit을 10억회로 지정해둔다면 이 에러가 해결된다

---

실행 및 마무리

Test case 1 : 5 / Test case 2 : 1

정상적으로 출력 되는 모습을 볼 수 있다!

---

End