[C++] 백준 1697번: 숨바꼭질 (BFS, DP)

1697번: 숨바꼭질

---

문제 이해하기

 문제의 요구사항은 다음과 같습니다.

이동 방향이, 현재 위치 X에 대해 X - 1, X + 1, X * 2 일 때, 위치 N에서 위치 K에 도달하는 최단 거리를 구하여라.

---

시간복잡도 어림하기

BFS 알고리즘

 가중치가 같은 (모든 이동에 대한 시간이 1초) 최단 거리 문제이므로 BFS로 해결할 수 있습니다. 가능한 좌표가 최대 100,000이므로 최악의 경우 100,000 좌표를 모두 탐색합니다. 이는 제한 시간 내에 문제를 해결하기 충분한 수치이므로 BFS 알고리즘을 사용하여 문제를 해결할 수 있습니다.

 

브루트 포스 알고리즘

 한 좌표당 이동 가능한 지점이 세 개 이므로 한 좌표 당 세 개의 경우의 수를 가집니다. 모든 좌표가 세 개의 경우의 수를 가지는 것은 아니지만, 가능한 좌표가 최대 100,000 이므로 3의 제곱수의 실행 횟수를 가지는 브루트 포스 알고리즘으로는 문제를 해결할 수 없습니다.

 

DP 알고리즘

 각 상태를 메모리에 저장할 수 있고, 현재 문제를 해결하기 위해 이전 상태를 활용할 수 있을 것으로 보입니다. DP에 현재 위치 idx에 도달하는 최단거리를 담는다고 하면, idx에 도달 가능성이 있는 이전 상태를 활용해 한 번의 탐색으로 DP 배열을 완성할 수 있습니다.

 

 이번 글에서는 DP 알고리즘을 중심으로 문제를 해결해보겠습니다.

---

알고리즘 설계하기

 DP 배열에 idx까지 도달하는 최단 경로를 담는다고 합니다. 그렇다면 DP[idx]는 어떻게 구할 수 있을까요?

어떤 지점 idx에 도달가능한 경우의 수
1. idx - 1 에서 X + 1 이동으로 idx에 도달
2. idx + 1 에서 X - 1 이동으로 idx에 도달
3. idx / 2 에서 X * 2 이동으로 idx에 도달 (이때, idx는 짝수)

 위 경우의 수를 보면 idx에 도달할 수 있는 방법은 총 세 가지 입니다. 그렇다면 다음과 같이 DP 알고리즘을 사용할 수 있겠네요.

for(int i = n + 1; i <= k; i++){
	dp[i] = min(dp[i - 1] + 1, dp[i + 1] + 1);
    if(i % 2 == 0) dp[i] = min(dp[i], dp[i / 2] + 1);
}

 위 코드를 실행해보시면 아시겠지만, 이는 정상적으로 작동하지 않습니다. n - 1부터 0까지의 DP 값이 모두 0이기 때문입니다. 따라서 n보다 작은 위치에 대해 DP값 초기화를 먼저 해주어야 합니다.

 

 현재 위치 n에서 n보다 작은 위치 m에 도달하려고 할 때, 최단 거리는 X - 1이동을 하는 것이기 때문에 n - m입니다. 따라서 미리 다음과 같이 초기화합니다.

for(int i = 0; i <= n; i++)
	dp[i] = n - i;

 

 이렇게 초기화 구문까지 넣어주면 문제가 해결이 될까요?

 

 아쉽게도 여전히 해결되지 않습니다. 아래 예시를 살펴봅시다.

n = 2, k = 5 일때,
초기  DP 배열 : 2 1 0 0 0 0 0 0 0 0 ... 0

i = 3일때,
dp[2]은 0, dp[4]도 0 이므로 1로 갱신, 3은 짝수가 아니므로 다음 인덱스 탐색
DP 배열 :2 1 0 1 0 0 0 0 0 0 ... 0

i = 4일때,
dp[3]은 1, dp[5]는 0, 4는 짝수이므로 dp[4 / 2] = 1, 따라서 dp는 최솟값인 0  + 1 = 1로 갱신
DP 배열 : 2 1 0 1 1 0 0 0 0 0 ... 0

i = 5일때,
dp[4]는 1, dp[6]은 0, 5는 짝수가 아니므로 다음 인덱스 탐색 따라서 최솟값 + 1 = 1 로 갱신
DP 배열 : 2 1 0 1 1 1 0 0 0 0 ... 0

 뭔가 이상한 점이 보이시나요? 바로 현재 인덱스 i보다 큰 값은 항상 0이기 때문에 나타나는 문제입니다.

 가장 처음에 DP를 0이 아닌 INF로 초기화 해도, 인덱스 i보다 큰 위치에서 현재 위치에 도달하는 경우는 DP에 반영하지 못하는 문제가 발생합니다.

 

 이러한 문제가 발생하는 이유는 dp[i]을 갱신하기 위해 아직 확정되지 않은 값(dp[i + 1])을 사용했기 때문입니다. 이와 같은 문제를 해결하기 위해서는 dp[i]를 갱신하기 위해 사용하는 상태 값을 모두 i보다 작은 위치 값을 사용해야 합니다.

 

 그렇다면 다시 idx에 도달 가능한 경우의 수를 나누어 봅시다.

어떤 지점 idx에 도달 가능한 경우의 수
1. idx - 1에서 X + 1 이동으로 idx에 도달
2. idx가 짝수일 때, idx / 2에서 X * 2 이동으로 idx에 도달
3. idx가 홀수 일때, (idx - 1) / 2에서 X * 2이동, X + 1 이동으로 idx에 도달
4. idx가 짝수 일때, (idx + 1) / 2에서 X * 2이동, X - 1 이동으로 idx에 도달 

 이 네가지 경우로 나눌 수 있습니다. 현재 위치 idx보다 작은 값은 이미 확정되었기 때문에, 이동의 시작 위치가 idx보다 작은 위치에서 출발하도록 해야합니다. 코드로는 다음과 같습니다.

for(int i = n + 1; i <= k; i++){
        if(i % 2 == 0) dp[i] = dp[i / 2] + 1;
        else
            dp[i] = min(dp[(i - 1) / 2] + 2, dp[(i + 1) / 2] + 2);
        dp[i] = min(dp[i], dp[i - 1] + 1);
    }

 

 이처럼 DP 알고리즘을 사용할 때에는 dp[i] 값을 갱신 시키기 위해 사용하는 dp 값들이 확정된 값들인지 확인하는 것이 중요합니다.

---

알고리즘 구현하기

 최종 코드는 다음과 같습니다.

#include <iostream>
using namespace std;

int n, k, dp[100004];
int main() {
    cin >> n >> k;
    
    /*k가 n 이하일 때, 최단거리 출력 후 종료*/
    if(k <= n){
        cout << n - k; return 0;
    }
    
    /*n보다 작은 위치 최단거리 초기화*/
    for(int i = 0; i <= n; i++)
        dp[i] = n - i;
    /*dp 갱신*/
    for(int i = n + 1; i <= k; i++){
        if(i % 2 == 0) dp[i] = dp[i / 2] + 1;
        else
            dp[i] = min(dp[(i - 1) / 2], dp[(i + 1) / 2]) + 2;
        dp[i] = min(dp[i], dp[i - 1] + 1);
    }
    cout << dp[k];
    return 0;
}​

 주요 로직은 설계 단계와 동일합니다.

 

추가 BFS 코드

 이 문제는 가중치가 동일한 최단거리 문제이므로 BFS로도 문제를 해결할 수 있습니다. 코드 설명은 주석으로 대체하겠습니다.

#include <iostream>
#include <queue>
using namespace std;

int n, k, ret, visited[200004];
queue<int> q;
int main() {
    cin >> n >> k;
    
    /*k가 n 이하인 경우, 바로 최단거리 출력*/
    if(k <= n){
        cout << n - k; return 0;
    }
    
    q.push(n); visited[n] = 1; //처음 위치 방문
    int pos;
    while(!q.empty()){
        pos = q.front(); q.pop();
        /*다음 위치 탐색*/
        for(int next : {pos + 1, pos - 1, pos * 2}){
            if(next < 0 || next > 100000 || visited[next]) continue; //유효성 검사
            q.push(next); visited[next] = visited[pos] + 1; //최단거리 갱신 및 다음위치 방문
        }
    }
    cout << visited[k] - 1; //시작 최단거리가 1이므로 1을 다시 빼줌
    return 0;
}

---