[백준] 1012: 유기농 배추 python 구현 / DFS, RecursionError

문제

한나가 배추를 재배하는 땅은 고르지 못해서 배추를 군데군데 심어 놓았다. 배추들이 모여있는 곳에는 배추흰지렁이가 한 마리만 있으면 되므로 서로 인접해있는 배추들이 몇 군데에 퍼져있는지 조사하면 총 몇 마리의 지렁이가 필요한지 알 수 있다. 

 

=> 인접한 배추들의 뭉치(?)의 개수를 세는 문제 

풀이

지난 시간에 푼 단지 번호 붙이기 문제와 비슷한 유형이기도 해서 이번엔 DFS로 한번 풀어보고 싶었다.. 그런데 이 선택을 후회한다 ㅠㅠ 

기본적으로 python 에서 설정한 재귀의 최대 깊이는 1000이다. 

그러나 본 문제에서, 모든 칸에 배추 흰 지렁이(1) 가 있다면, 재귀함수 자체를 50*50 = 2500호출하게된다.

 ===> 해당 과정에서 RecursionError

질문 게시판에서 찾아봤을 때 재귀의 깊이를 2501개로 설정해두면 돌아간다고 했는데 나는 왜 안돌아 가는지 자꾸 오류가 났다..! 그래서 그냥 애초에 큰 수로 설정했더니 돌아갔습니다 !

import sys    
sys.setrecursionlimit(5000)

이런 유형의 문제는 BFS로 풀어야 함을 깨닳았다...

 

또한 지금까지는 정사각 유형의 Map을 사용하다가 직사각을 만나게되니 파이썬 이차원 리스트의 인덱싱에 문제가 좀 있었다. 헷갈리지 않도록 주의해야할 것 같다.

CODE

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

def dfs(x, y):   
    # x축 +1 -1, y축 +1 -1
    dx = [0, 0, -1, 1]
    dy = [1, -1, 0, 0 ]

    # 경우의 수 탐색
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        # 범위를 벗어난 경우 pass
        if nx<0 or ny<0 or nx>(n-1) or ny>(m-1): continue
        # 배추가 존재하는 경우 
        if Map[nx][ny] == 1:
            Map[nx][ny] = -1
            dfs(nx, ny)


t = int(input())
result = []
for _ in range(t):
    ## 입력 
    m, n, k = map(int, input().split()) # 가로, 세로, 배추 개수
    Map = [[0]*m for _ in range(n)]
    for _ in range(k):
        x, y = map(int, input().split()) # x < M, y < N
        Map[y][x] = 1

    cnt = 0
    ## 실행
    for i in range(n):   # 세로
        for j in range(m): # 가로
            if Map[i][j] == 1:
                Map[i][j] = -1
                dfs(i, j)
                cnt += 1
    result.append(cnt)

for i in result:
    print(i)