백준 1012 - 유기농 배추 (Python3)

코드

import sys
sys.setrecursionlimit(10 ** 5)

T = int(input())

for _ in range(T):
    M, N, K = map(int, input().split())
    graph = [[0] * M for _ in range(N)]

    for _ in range(K):
        a, b = map(int, input().split())
        graph[b][a] = 1

    cnt = 0

    def dfs(y, x):
        if x < 0 or x >= M or y <0 or y >= N:
            return False

        if graph[y][x] == 1:
            graph[y][x] = 0

            dfs(y-1,x)
            dfs(y,x-1)
            dfs(y+1,x)
            dfs(y,x+1)
            return True
        return False

    for i in range(N):
        for j in range(M):
            if dfs(i,j) == True:
                cnt += 1
            
    print(cnt)    

문제 해설

DFS로 문제를 해결하였다. 기능의 구현보다 x, y 값 설정에서 애를 먹었는데 일반적인 문제들과 다르게 x, y의 좌표가 반대로 설정돼있었다. (out of index 계속 발생…) 또한 DFS로 구현하다 보니 재귀함수 호출 횟수 제한으로 에러가 발생하여 sys.setrecursionlimit을 사용하여 제한을 늘려줘서 정답으로 인정받았다.