백준 1012 파이썬(DFS/BFS)

이번 문제는 이전 단지번호 붙이기(2667번)에서 사용되었던 방법을 이용하면 풀수 있다.

아니, 문제 자체는 오히려 더 쉽다.

 

하지만 이번 문제에서도 에러를 만나게 되었는데 

바로 런타임에러(recursion error)이다.

 

이놈을 만나고 나서 계속 코드를 하나하나 뜯어보았다.

분명히 코드엔 잘못된 부분이 없는것 같다.

base case조건도 분명하게 걸어놨고

테스트 입력값에서도 잘 돌아갔다.

 

구글링을 통해서 찾아보니 재귀의 깊이제한을 설정해줘야 한다는 것을 알았다.

파이썬은 기본 재귀 깊이 제한이 1000으로 매우 얕다고 한다.

따라서 재귀를 사용하여 문제를 풀 때에는 위의 코드를 넣어주어 재귀에러가 나는것을 막아주어야 한다.

이후에 코딩테스트에서도 이부분은 필수라고도 적혀있으니 기왕이면 외워두는게 좋을 것 같다.

import sys
sys.setrecursionlimit(10 ** 6)

---

코드

# 1012 유기농 배추 - dfs/bfs탐색

import sys
sys.setrecursionlimit(10 ** 6)

t = int(input())

def dfs(x,y):
    if x < 0 or x > n-1 or y < 0 or y > m-1:
        return False
    if graph[x][y] == 1:
        graph[x][y] = 0
        dfs(x-1,y) # 상
        dfs(x+1,y) # 하
        dfs(x,y-1) # 좌
        dfs(x,y+1) # 우
        return True
    return False

for _ in range(t):
    m,n,k = map(int,input().split()) # m=가로, n=세로, k=배추개수
    graph = [[0]*(m) for _ in range(n)]
    for _ in range(k):
        a,b = map(int,input().split())
        graph[b][a] = 1
    
    res = 0
    for y in range(m):
        for x in range(n):
            if dfs(x,y) == True:
                res += 1

    print(res)