BFS 탐색 중 안전하게 pruning(가지치기) 할 수 있는 기준
요즘 열심히 알고리즘 문제를 하루에 한 문제씩이라도… 푸는 중이다. DFS, BFS 문제를 기계처럼 풀다가 내겐 좀.. 생소했던 문제 하나(아래에서도 언급할 백준 14226(이모티콘) 문제)를 풀다가 가지치기를 도대체 어떻게 할까..에 대해서 정말 오랜만에 고민했던 것 같다. 이 문제가 BFS로 적당히 가지치기 기준 세워가며 시간 초과 안 당하고 풀어야 했던 문제라.. GPT 형님과 함께 안전하게 pruning(가지치기)를 할 수 있는 기준에 대해서 알아봤다🤔🤪
✂️“안전한 pruning”이란?
정답(또는 최적해)을 절대 놓치지 않으면서, 탐색을 줄이는 것을 의미한다
즉, “이 경로는 정답과 무관하다”는 명백한 근거가 있어야 가지치기를 할 수 있다는 것이다!
- “더 이상 최적이 될 수 없는 경로”
- “이미 이 상태를 더 짧은 시간에 방문한 적 있음”
✔️BFS에서 pruning이 필요한 이유
- BFS는 가장 먼저 도달한 경로가 최단 거리다 → 이건 BFS의 가장 큰 장점이다
그런데, 모든 경로를 Queue에 넣고 탐색하면 상태 수가 기하급수적으로 증가 → 이건 BFS의 가장 큰 단점
⇒ 모든 경로를 Queue에 넣고 탐색하게 되면, 같은 상태를 또 방문할 수 있기 때문에 중복 제거, 즉 가지치기가 필요하다!
✔️BFS에서 안전한 pruning의 대표 기준들
🧩 기준1. 이미 방문한 상태는 다시 방문하지 않는다.
1
if (visited[nextX][nextY]) continue;
- 가장 기본적이면서 안전한 가지치기 방법이다
- 우리가 문제 풀 때 자주 사용하는 visited 배열이 바로 이 기준을 사용하는 것이다!
- 해당 과정을 거치지 않는다면, 같은 상태를 여러 번 방문하게 된다
- 시간 초과가 발생할 가능성 매우 높다!!
🧩 기준2. 이미 더 짧은 시간에 도달한 상태라면 무시한다.
가중치가 있는 BFS(ex. 다익스트라, DP-BFS)나 DP와 BFS를 섞은 유형에서 굉장히 자주 등장하는 유형이다. 이게 무슨 뜻인지 모르겠다면.. 아래 예시를 하나 보자.
어떤 상태 A에 3초 만에 도달 한 적이 이미 있는데, 다른 경로를 통해 5초 걸려서 또 A에 도달했다면?
이미 3초짜리 경로가 있는데 굳이 5초짜리 경로를 다시 탐색할 필요가 없겠지.. 그래서, 그 경로를 가지치기 한다는 것이다!
아래는 이 기준을 적용한 대표적인 문제인 백준 12852번의 간단한 js 풀이다. 한 번 살펴보며 이해를 해보자!
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
function minOperations(N) {
// 최소 연산 횟수를 저장할 배열 (Infinity로 초기화)
const dist = new Array(N + 1).fill(Infinity);
// 시작 숫자 1은 연산 0번으로 도달
dist[1] = 0;
// BFS를 위한 큐
const queue = [];
queue.push(1);
while (queue.length) {
const current = queue.shift();
// 가능한 연산: +1, *2
for (let next of [current + 1, current * 2]) {
if (next > N) continue;
/*
dist[x]는 숫자 x에 도달하는 데 필요한 최소 연산 횟수
아래 코드는 이미 더 짧은 연산 횟수로 next에 도달한 적이 있다면, 그 이후 경로는
탐색하지 않고 가지치기(pruning)하는 역할을 한다.
*/
if (dist[next] <= dist[current] + 1) continue;
// 더 짧은 경로로 도달했으므로 갱신
dist[next] = dist[current] + 1;
queue.push(next);
}
}
return dist[N];
}
// 예시 실행
const N = 10;
console.log(`1에서 ${N}까지 가는 최소 연산 횟수:`, minOperations(N));
🧩 기준3. 문제 조건에서 정답이 나올 수 없는 경로는 탐색하지 않는다.
문제 조건이나 목표를 기준으로, 탐색할 필요가 없는 상태는 미리 잘라내자.
다음 기준을 적용할 수 있는 좋은 예시 문제가 있다. 바로, 백준의 14226번 문제.
이 문제의 목표는 이모티콘 S개를 화면에 만드는 것이다. 문제의 조건 중, 가능한 연산 중에는 화면의 이모티콘을 1개씩 없애는 것 빼고는, 화면의 이모티콘을 없애는 방법이 없다.
그러하다면, 화면에 이미 S보다 훨씬 많은 이모티콘이 있다면, 더 이상 그 상태는 의미가 없을 거다(1개씩 없애서 어느 세월에 없애냐…)
→ 이런 경우에 대해서는 탐색할 필요 없이 바로 짤라내라는 거다.
1
if (value[0] > S * 2) continue; // 화면 이모티콘 너무 많으면 건너뛰기
요약하자면, 목표 이상으로 커져 버린 상태는 무조건 불리하니까 바로 컷! 하자는 거다.
🧩 기준4. 이전보다 “열등한” 상태는 무시한다
같은 결과를 만들 수 있더라도, 어떤 상태는 더 “불리한 조건”일 수 있다.
위에서 언급 했던 백준의 14226번 문제를 다시 살펴보자.
화면 = 5, 클립보드 = 5인 상태와 화면 = 5, 클립보드 = 1인 상태가 있다고 했을 때, 목표가 이모티콘을 더 늘리는 거라면, 클립보드에 5개가 있는 게 훨씬 유리할 거다!å
1
2
// 기존에 화면=5, 클립보드=5로 도달한 적이 있다면,
// 화면=5, 클립보드=1은 더 불리하니 굳이 탐색할 필요 없음!
이런 상태를 visited 배열에서 따로 구분해 놓지 않으면 같은 상태를 불리한 조건으로 여러 번 탐색하게 된다.
요약하자면, 문제 상황을 잘 분석해서 “같은 목표를 향해 가는 더 나쁜 상태”를 판단할 수 있다면, 과감히 버리자는 거다!
📝실전에서 pruning 범위를 잡는 전략 4가지
지금까지 BFS에서 안전한 대표적인 가지치기 기준 4가지를 알아봤다. 이를 기준으로 실전에서 가지치기 범위를 잡는 전략 4가지를 알아보자.
입력 범위 기반으로 탐색 경계 정하기
→ 문제 조건이 이미 범위를 제한해 줬다면, 그 범위를 넘는 상태는 탐색할 필요 없음.
(ex. S ≤ 1000이면 화면, 클립보드 둘 다 1000 넘지 않도록 제한)
도달 불가능하거나 무의미한 상태는 잘라내기
→ 음수 좌표, 벽 뚫기 등 문제 조건을 위반할 경우, 탐색하지 않는다.
(ex. 미로 탈출 문제에서 벽이면 가지 않음)
이미 최적이 아닌 경로는 skip한다 (비효율적인 상태 제거)
→ 더 많은 연산, 더 많은 이동 거리, 더 많은 비용 등은 무조건 느림
(ex. 같은 지점에 왔는데 더 많은 시간이 걸렸다면, 그 경로는 무시함)
탐색 깊이나 경과 시간에 제한이 있다면 초과 시 중단
→ 재귀 깊이, 시간 초과 등 실전 문제 제약에 맞춰 가지치기
BFS 뿐만 아니라 DFS, 재귀 등의 다양한 문제 풀이에서 시간/메모리 초과 등을 방지하기 위해 가지치기가 필요한 경우가 많다. 앞으로도 문제마다 탐색 범위를 줄일 수 있는 논리를 하나씩 찾는 습관이 매우 중요할 것 같다!!
