💡 백준 1012:
DFS 탐색
🌱 코드 in Python
알고리즘: DFS
import sys
sys.setrecursionlimit(10**6) # 재귀 한계 재설정
input = sys.stdin.readline
t = int(input())
global cnt
def dfs(cab, i, j):
global cnt
cab[i][j] = 0
cnt += 1 # 찾은 배추 개수 카운팅
if i > 0 and cab[i - 1][j]: # 4방위 전부 탐색
dfs(cab, i - 1, j)
if i + 1 < n and cab[i + 1][j]:
dfs(cab, i + 1, j)
if j > 0 and cab[i][j - 1]:
dfs(cab, i, j - 1)
if j + 1 < m and cab[i][j + 1]:
dfs(cab, i, j + 1)
for _ in range(t):
m, n, k = map(int, input().split())
cab = [[0] * m for i in range(n)]
for _ in range(k):
x, y = map(int, input().split())
cab[y][x] = 1
ret = 0
cnt = 0
for i in range(n):
for j in range(m):
if cab[i][j] == 1:
dfs(cab, i, j)
ret += 1
if cnt == k: # 배추를 다 찾았으면 탐색 종료
break
print(ret)이번 문제는 배추 밭에서 서로 연결되지 않은 배추가 몇 개 구역으로 나뉘어있는지 찾는 문제였다
밭에서 배추를 찾은 경우에 그와 연결되어있는 배추를 모두 찾아 체크해둬야 다음에 또 탐색하지 않을 수 있기 때문에,
BFS 혹은 DFS로 배추밭을 탐색하여야 한다
이 문제는 배추밭을 2차원 배열로 가공하고 배추가 심어져 있는지 여부를 1, 0으로 확인하다보니 별도의 방문 확인 배열을 만들지 않고
배추밭의 정보를 모두 0으로 바꿔가며 해결하는 것으로 했다
cnt 변수의 경우 딱히 두지 않고 전체 배열을 탐색해도 문제는 없으나,
배추를 다 찾은 경우에 쓸데없는 반복문을 돌지 않기 위해 중간에서 종료시켜주었다
연결된 배추를 모두 찾는 dfs 부분에서는 배열 인덱스를 넘어서지 않는 한에서 탐색하는 것이 중요하며,
나의 경우 재귀문을 통해 dfs 방식을 구현하였다
위, 아래, 왼쪽, 오른쪽 순서로 탐색하며 해당 방향에 배추가 있다면 그 방향의 depth를 계속 해서 추적하게 된다
그러나 여기서 중요한 것은!!!!!
파이썬은 재귀문의 깊이가 1,000으로 정해져 있어 그 이상의 재귀문을 돌 경우 런타임에러가 발생하게 된다 또르륵
어떻게 알았냐구요..? 저도 알고싶지,,, 아... 아니.. 알아야지..
아무튼... 이 한계를 풀 수 있는 함수가 있는데,
sys.setrecursionlimit(limit_number) 바로 이 함수이다
limit_number에 원하는 횟수를 넣어주면 그 횟수까지 재귀를 실행할 수 있게 된다
🤔 그런데 사실 재귀가 어느정도의 깊이로 진행되는지 낵아 알게 모냔말이다...
어떻게 알지?! 또르륵 ㅠ
🧠 기억하자
- 파이썬 재귀에는 한계가 있다!
- 다음에는 재귀 깊이에 대해 공부할 수 있는 시간을 가지면 좋겠다
- sys.setrecursionlimit(limit_number) 를 기억하자
