백준 - 1012번(DFS,BFS 문제지만 완전 탐색으로 품)

바로 전에 풀었던 백준 2067번과 90% 유사한 문제다.

 

다른 점이 있다면 여기서는 입력받은 좌표값을 1로 치환해주고 전체 리스트를 0 을로 감싼 다음에 십자가 모양으로 전체 탐색을 한다.

import sys
sys.setrecursionlimit(10000)
t = int(sys.stdin.readline())

def count(arr,i,j,tmp):
    arr[i][j] = '0'
    tmp.append(i)
    tmp.append(j)

    if arr[i + 1][j] == '1':
        if i + 1 >= 0 and j >= 0:
            count(arr, i + 1, j, tmp)

    if arr[i - 1][j] == '1':
        if i - 1 >= 0 and j >= 0:
            count(arr, i - 1, j, tmp)

    if arr[i][j + 1] == '1':
        if i >= 0 and j + 1 >= 0:
            count(arr, i, j + 1, tmp)

    if arr[i][j - 1] == '1':
        if i >= 0 and j - 1 >= 0:
            count(arr, i, j - 1, tmp)


for i in range(t):

    m, n, v = sys.stdin.readline().split()
    m = int(m)
    n = int(n)
    v = int(v)

    arr = []
    ans = []

    arr = list(['0'] * (m + 2) for _ in range(n + 2))

    for i in range(v):
        x = list(input().split())
        arr[int(x[1]) + 1][int(x[0]) + 1] = '1'

    tmp = []
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if arr[i][j] == '1':
                count(arr, i, j, tmp)
                ans.append(tmp)
                tmp = []

    print(len(ans))

기존 설정이면 파이썬은 재귀의 깊이가 정해져있기 때문에 리커젼에러가 발생한다.

따라서  sys모듈에 있는 setrecursionlimit 모듈을 불러와서 재귀의 최대 깊이를 변경해주자.