백준 13913번 숨바꼭질 4 (C++)

문제 링크 : www.acmicpc.net/problem/13913

13913번: 숨바꼭질 4

BFS문제이며, 문제를 대충 읽고 풀었다가는 아래 유의 사항을 놓칠 수 있다.

 

1. 둘의 위치가 같은 경우

5 5 // n=5, k=5
0 // the number of movement
5 // your accumulated position

2. 위치 출력시 무조건 첫 번째는 출발 지점이 나올 수 밖에 없다.

 

---

 

문제 풀이는 다음과 같다. 

1. n과 k를 입력받는다. 만약 두 숫자가 같을 경우, 곧 바로 0과 첫 위치를 출력시키고 종료한다.

2. BFS를 진행한다.

        for(int i=0; i<3; i++){
            if(i==2) temp=pos*2;
            else temp=pos+m[i];
            if(temp<0||temp>=MAX) continue; // 이러면 더이상 탐색 필요 X
            else if(arr[temp]==0){
                arr[temp] = arr[pos]+1;
                path[temp] = pos;
                q.push(temp);
            }
        }

temp = pos(현위치)+1, pos-1, pos*2를 해서 움직인 값을 아직 방문한 적이 없을 경우==0, arr[temp] = arr[pos]+1로 저장해준다. 만약 방문한 적이 있을 경우 !=0, 이미 해당 경로를 가기 위한 최소값이 정해져있다는 의미이므로 별다른 진행을 안하면 된다.

또한 이동 경로를 저장해주기 위해, path[temp] = pos를 저장해준다. 이렇게해서 꼬리물기처럼 방문했던 경로들을 하나하나 나열할 수 있게 된다. 이렇게 모든 과정을 거치고 이동완료한 값을 큐에 넣어준다.

 

3. 만약 큐에 삽입된 값이 목적지에 도달했을 경우, 다음 코드를 실행한다.

        if(pos==k){ // 정답
            cout << arr[pos]<< "\n";
            stack<int> ans;
            ans.push(pos);
            for(int i=pos; i!=n; i=path[i]) ans.push(path[i]); // 주의
            while(!ans.empty()){
                cout << ans.top() << " ";
                ans.pop();
            }
            cout << "\n";
            exit(0);
        }

먼저 현재 위치인 K를 스택에 넣어준다.

그리고 이동값을 출력시킨다. 그리고 스택을 만들어 현 지점에서 거쳐간 과거지점들을 모두 삽입해준다.

스택에 삽입되는 경로들의 흐름은 아래 예시를 참고하면 된다.

5	10	20	40	80	160	161
5(n=5)	5	10	20	40	80	160

맨 오른쪽부터 왼쪽까지의 거쳐간 경로들을 하나하나 출력하면, 160 -> 80 -> 40 -> 20 -> 10 -> 5 가 나온다.

맨 왼쪽의 path[5] = 5는 출력되지 않는다. for문에 i!=n이라는 조건을 걸어뒀기 때문이다.

이렇게 해서 맨 처음에 저장한 현재 위치 k와 합체해서, 161 -> 160 -> 80 -> 40 -> 20 -> 10 -> 5가 저장되고, 스택의 특성상 값은 거꾸로 출력된다.

 

#include <iostream>
#include <queue>
#include <stack>
#define MAX 100001
using namespace std;

int n,k,pos,temp,m[]={-1,1,0},path[MAX],arr[MAX];
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n >> k;
    if(n==k){
        cout << 0 << "\n" << n << "\n";
        exit(0);
    }
    queue<int> q;
    q.push(n);
    while(!q.empty()){
        pos = q.front();
        q.pop();
        if(pos==k){ // 정답
            cout << arr[pos]<< "\n";
            stack<int> ans;
            ans.push(pos);
            for(int i=pos; i!=n; i=path[i]) ans.push(path[i]);
            while(!ans.empty()){
                cout << ans.top() << " ";
                ans.pop();
            }
            cout << "\n";
            exit(0);
        }
        for(int i=0; i<3; i++){
            if(i==2) temp=pos*2;
            else temp=pos+m[i];
            if(temp<0||temp>=MAX) continue; // 이러면 더이상 탐색 필요 X
            else if(arr[temp]==0){
                arr[temp] = arr[pos]+1;
                path[temp] = pos;
                q.push(temp);
            }
        }
    }
    return 0;
}

 

이 문제 자체는 그리 어렵지 않았다. 다만, 최근에 풀었던 LeetCode 45. Jump Game II와 유사성을 보인 점에서 흥미가 느껴졌다.

Jump game II은 DP를 활용한 Greedy로 풀었고, 이 문제는 전형적인 BFS를 통해 풀었다.

두 문제의 차이점은, Jump Game에서는 점프 할 수 있는 값이 불규칙적, 즉, 상황에 따라 달라진다는 점이며, 반대로 이 문제는 점프의 횟수가 고정되어있다는 점이다.