[알고리즘] 백준 1012 파이썬 풀이

유기농 배추

 

흔하게 보이는 문제 패턴입니다. 1은 배추가 있는 장소이고 배추가 붙어있다면 배추흰지렁이는 한마리가 필요합니다. 결국, 배추 무더기의 개수를 묻는 문제입니다. 처음 다음과 같이 풀이했습니다.

 

t = int(input())
for _ in range(t):
    count = 0
    m, n, k = map(int, input().split())
    graph = [[0] * n for _ in range(m)]
    for _ in range(k):
        x, y = map(int, input().split())
        graph[x][y] = 1

    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]

    def dfs(x, y):
        if x < 0 or y < 0 or x >= m or y >= n or graph[x][y] == 0:
            return

        graph[x][y] = 0

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            dfs(nx, ny)


    for i in range(m):
        for j in range(n):
            if graph[i][j] == 1:
                count += 1
                dfs(i, j)
    print(count)

 

하지만 런타임 에러(RecursionError) 가 나왔습니다. 저는 자주 헷갈리는 x, y의 방향이 잘못되었나 보았지만 잘못된건 아니었습니다. 그렇게 구글링을 계속 하던 도중 다음 코드를 추가해보라는 조언을 들었습니다.

 

import sys
sys.setrecursionlimit(10000)

setrecursionlimit은 파이썬의 스택깊이 제한을 해제하는 메서드입니다. depth가 너무 깊어져서 나왔던 에러였습니다.

위 두 줄의 코드는 깊이 제한을 10000으로 늘리겟다는 뜻입니다.

 

참고로 파이썬의 재귀 깊이 제한은 1000이라고 합니다!!

 

다음은 해결한 전체 코드입니다.

 

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10000)
t = int(input())
for _ in range(t):
    count = 0
    m, n, k = map(int, input().split())
    graph = [[0] * n for _ in range(m)]
    for _ in range(k):
        x, y = map(int, input().split())
        graph[x][y] = 1

    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]

    def dfs(x, y):
        if x < 0 or y < 0 or x >= m or y >= n or graph[x][y] == 0:
            return

        graph[x][y] = 0

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            dfs(nx, ny)


    for i in range(m):
        for j in range(n):
            if graph[i][j] == 1:
                count += 1
                dfs(i, j)
    print(count)