[boj] 유기농 배추_1012

dfs를 통해 배추의 묶음을 판단하는 문제이다.

2667번 단지번호 붙이기와 문제의 접근법이 완전히 동일하게 dfs로 접근하면 어렵지 않게 풀 수 있다.

 

다른점이 있다면, 이 문제는 여러 테스트 케이스에 대해서 다르게 출력할 수 있게 따로 설정해 주어야 한다는 점이다.

 

# 유기농 배추
import sys
sys.setrecursionlimit()

def dfs(par_y, par_x):
    if par_x >= M or par_y >= N or par_x <= -1 or par_y <= -1:
        return False
    elif graph[par_y][par_x] == 1:
        graph[par_y][par_x] = 0
        dfs(par_y+1, par_x)
        dfs(par_y-1, par_x)
        dfs(par_y, par_x+1)
        dfs(par_y, par_x-1)
        return True
    else:
        return False

result = []
count = 0

T = int(input())

for _ in range(T):
    # 가로길이 M, 세로길이 N, 배추가 심어진 위치의 개수 K
    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

    # Test Case 수 만큼 돌리기
    for k in range(T):
        for i in range(M):
            for j in range(N):
                if dfs(j, i) == True:
                    count += 1
    
    result.append(count)

    graph = [[0] * M for _ in range(N)]
    count = 0

for node in result:
    print(node)

print(sys.getrecursionlimit())

중간에 보면 3중 루프가 사용되었는데, 문제 조건상 주어지는 조건의 모든 수를 고려해보니 큰 무리 없이 통과될 것이라고 짐작해 3중 루프를 사용했다.

 

처음 테스트 케이스 2개는 모두 통과했었으나, 채점시 런타임 에러가 발생했다.

 

질문 검색을 통해 재귀 한도의 문제임을 알았고 sys 라이브러리를 import해 재귀 한도를 늘려주니 해결이 되었다.

 

 

setrecursionlimit() 을 통해 재귀 한도를 늘려주지 않았을 때에는 (즉, 기본 상태에서는) 재귀 한도가 1000으로 출력되었다.

 

문제 조건에서 가로 세로의 길이가 50이 최대라고 하여 재귀 한도를 2500까지 늘려주면 해결 될 것이라고 생각했으나 2503까지 늘려주어야 해결되었다. 왜 2500이 아니라 2503인지는 잘 모르겠다.