[코딩테스트, 더 이상 미룰 수 없다] BOJ 2468 - DFS를 도구로 바라보기

 

이 문제를 풀면서 가장 크게 느낀 점은
단순히 DFS를 쓰는 문제가 아니라,

“DFS를 어떻게 바라보느냐”에 대한 문제였다.

 1. 처음 느낀 위화감

---

쉬운 난이도의(내가 알던) DFS

그래프를 한 번 탐색해서 끝

• 미로 탐색
• 특정 노드까지 도달 가능 여부

👉 DFS = 문제 해결 자체

---

그런데 이 문제는

DFS를 계속 여러 번 돌림
+ 조건까지 붙음 (높이 > rain)

👉 뭔가 DFS가 아닌 다른 알고리즘처럼 느껴짐 -> DP인가? 생각함

---

2. 핵심 깨달음

 

❗ DFS는 알고리즘이 아니라 “탐색 도구”다

 

 

DFS = “연결된 것들을 한 번에 처리하는 도구”

---

3 . 안전 영역 문제에서 DFS의 역할

이 문제에서 DFS는 이렇게 사용된다.

---

🔍 DFS의 실제 역할

1. 안 잠긴 칸 발견
2. DFS로 연결된 칸 전부 방문 처리
3. → 영역 1개 제거

👉 즉,

DFS 한 번 = 영역 하나 처리

---

 

4. 왜 DFS가 “이상하게” 느껴졌는가

이 문제에서 느낀 위화감의 정체는 이거였다.

 

• DFS를 “한 번” 쓰는 게 아니라
• DFS를 여러 번 반복해서 사용

---

구조를 보면

비 높이 설정
    ↓
DFS 여러 번 → 영역 개수 세기
    ↓
비 높이 변경
    ↓
다시 DFS 반복

👉 이건 DFS 자체가 아니라

“DFS를 이용한 시뮬레이션”

 

 

5. 중요한 사고 전환

이 문제를 통해 가장 크게 바뀐 생각은 이것이다.

---

 Before

“DFS 문제니까 DFS를 어떻게 쓰지?”

 After

“이 문제에서 DFS는 어떤 역할을 하는 도구지?”

---

정리

DFS는 문제를 푸는 알고리즘이 아니라,
연결된 영역을 처리하기 위한 도구다.

---

 

 

추가로 마주한 문제: 런타임 에러

DFS를 구현했을 때 런타임 에러가 발생했다.

---

원인

파이썬은 재귀 깊이 제한이 기본적으로 1000이다.

이 문제는 최대 100 × 100 = 10000까지 깊어질 수 있어서
재귀 깊이 초과가 발생할 수 있다.

---

해결 방법

 

import sys
sys.setrecursionlimit(10000)