[BOJ][Python] #1012 유기농 배추

1012번: 유기농 배추

 

문제풀이

DFS 알고리즘을 적용하여 풀었다.

1. 입력받은 배추의 위치를 값 1로 설정한다.
2. 그래프를 돌다가 값이 1인 위치가 나오면 상하좌우를 확인한 후, 배추가 심어진 위치면 0으로 바꾼다.
3. 탐색이 완료되면 cnt += 1을 수행한다.
4. 2, 3번의 과정을 반복한 후, 최종적으로 필요한 배추흰지렁이 수(cnt)를 출력한다.

 

 

>> DFS 알고리즘 적용 풀이

import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline

def cabbage(x, y):
    a = [-1, 1, 1, -1]; b = [0, -1, 1, 1]

    if (0 <= x < n) and (0 <= y < m) and graph[x][y] == 1:
        graph[x][y] = 0
        for _ in range(4):
            x += a[_]
            y += b[_]
            cabbage(x, y)

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

    for _ in range(k):
        x, y = map(int, input().split())
        graph[x][y]=1

    for x in range(n):
        for y in range(m):
            if graph[x][y] == 1:
                cabbage(x, y)
                cnt += 1
    print(cnt)

---

시행착오

풀이를 제출할 때 계속 Recursion Error가 떴다.

이는 재귀와 관련된 에러로, python이 정한 최대 재귀 깊이보다 더 깊을 때 발생한다.

그도 그럴 것이, 처음엔 cabbage 함수 내에서 cabbage(x+1, y)와 같이 상하좌우 값을 모두 재귀로 체크했었다.

for문을 최대한 쓰지 않으려다 재귀를 남발한 상황이 되었다 🙃,,

 

파이썬이 정한 최대 재귀 깊이는 BOJ의 경우 1,000으로 되어 있는데

파이썬에 내장되어 있는 sys 라이브러리를 활용하여 그 한계값을 높여주면 된다.

 

결론적으로 이 문제를 해결하기 위해 아래와 같이 설정해주었다.

1. for문을 이용하여 x, y값을 바꾼 뒤, 상하좌우 값을 확인 ⇒ 재귀함수를 for문으로 대체하여 Recursion Error를 방지
2. sys.getrecursionlimit(100000) 추가

참고로 BFS로 풀면 런타임 에러가 안 뜬다고 하는데 다시 풀어봐야겠다 😇