[BOJ-1012] 유기농 배추 (Python)

🤒 문제

BOJ-1012 유기농 배추

💊 풀이

DFS 재귀함수로 풀이했다. BOJ-2776 단지 번호 붙이기 와 비슷해서 금방 풀 줄 알았는데, 오랜만에 풀어서 쉽지 않았다.

배추가 있는곳은 1로 표기했다.

DFS 재귀함수 설계

1. 배추가 없는 곳은 False 를 리턴하게 하여 카운팅 하지 않도록 한다.
2. 배추가 있다면, 즉, graph[x][y] == 1 이면 방문하여 0 으로 표시한다.
3. 상, 하, 좌, 우로 재귀 함수를 돌며 주변에 배추가 있는지 없는지 탐색한다.
4. 이렇게 상, 하, 좌, 우를 돌고 리턴이 되어 return True 구문까지 오게되면

if dfs(i, j):
	count += 1

부분의 DFS가 끝나게 되고 True 를 리턴 받아 count가 증가한다. 배추가 없는 곳에서도 DFS를 수행하여 쓸데없는 계산을 하지 않게끔 DFS전에 if 문을 추가하여 속도를 개선하려고 했다.

graph 입력 받을 때

파이썬 이중리스트 x, y 좌표가 미친듯이 헷갈렸다.. 혹시 나같은사람이 (없겠지만) 그래도 헷갈렸던 것 적어본다.

이중 리스트로 graph의 형태를 정했는데, 이 이중리스트는 이렇게 생겼다.

[[0, 0, 0, 0, 0, 0, 0, 0, 0, ...],
[0, 0, 0, 0, 0, 0, 0, 0, 0, ...],
[0, 0, 0, 0, 0, 0, 0, 0, 0, ...],
...
]

그래서 X, Y 좌표를 입력을 받으면 graph의 Y번째 리스트의 X번째 원소 를 의미하게 된다. 그래서 좌표를 거꾸로 넣어줘야 한다 ^^ 이게 왜 헷갈렸지 ㅋㅋ 이게 한번 꼬이니까 아무것도 모르게 되었다..

파이썬 재귀함수의 깊이

python3는 재귀함수 깊이가 1000까지로 얕다. 그래서 임의로 늘려줘야 한다.
sys모듈의 setrecursionlimit() 함수를 사용한다.

import sys
sys.setrecursionlimit(10 ** 8)

✨ 소스코드

import sys

sys.setrecursionlimit(10 ** 8)

def dfs(x: int, y: int):
    # 배추가 아님
    if x < 0 or x >= N or \
        y < 0 or y >= M :
        return False
    
    # 배추임
    if graph[x][y] == 1:
        graph[x][y] = 0 # 방문

        dfs(x, y + 1) # 상
        dfs(x, y - 1) # 하
        dfs(x - 1, y) # 좌
        dfs(x + 1, y) # 우 

        return True
    
    return False



T = int(input())
result = []

for i in range(T) :
    M, N, K =  map(int, sys.stdin.readline().split())
    graph = [[0] * M for i in range(N)] # 0 으로 초기화

    for _ in range(K):
        y, x = map(int, sys.stdin.readline().split())
        graph[x][y] = 1 # 배추 있는곳 1
    
    count = 0

    for i in range(N):
        for j in range(M):
            if graph[i][j] == 1:
                if dfs(i, j):
                    count += 1

    result.append(count)

for n in result:
    print(n)

참고로 pypy3로 제출하면 메모리 초과가 뜹니다.