[algorithm] 백준 - 숨바꼭질 4

이 문제는 bfs로 숨바꼭질과 비슷한 문제이다.

 

다른 점은 수빈이가 동생을 찾기위해 이동 경로를 출력해야한다는 것이다.

 

따라서 이동하고자 하는 위치를 인덱스로 하고, 현재 위치를 값으로 하는 배열을 추가하여 이문제를 해결했다.

 

조심해야할 부분은 수빈이의 위치인 n과 동생의 위치인 k가 같을 때 예외처리를 해주어야한다는 것이다.

예외처리를 하지 않을 경우

trace값이 k가 나올 때까지 무한루프를 돌면서 값들이 stack을 가득채워서 메모리 초과를 야기한다.

 

//숨바꼭질 4
#include <iostream>
#include <queue>
#include <stack>
using namespace std;

int weight[100001] = {0,};
int visited[100001] = {0,};
int trace[100001] = {0,};
void bfs(int n, int k){
    stack<int> stack;
    queue<int> q;
    q.push(n);
    visited[n] = true;
    while(!q.empty()){
        int node = q.front();
        q.pop();
        if(node == k){
            cout << weight[k] << "\n";
            int next = k;
            stack.push(k);
            while(trace[next] != n){
                stack.push(trace[next]);
                next = trace[next];
            }
            stack.push(n);
            while(!stack.empty()){
                cout << stack.top() << " ";
                stack.pop();
            }
        }
            int newLocation;
                newLocation = node + 1;
                if(newLocation <= 100000 && newLocation >= 0 && !visited[newLocation]){
                    weight[newLocation] = weight[node] + 1;
                    visited[newLocation] = 1;
                    trace[newLocation] = node;
                    q.push(newLocation);
                }
                newLocation = node - 1;
                if(newLocation <= 100000 && newLocation >= 0 && !visited[newLocation]){
                    weight[newLocation] = weight[node] + 1;
                    visited[newLocation] = 1;
                    trace[newLocation] = node;
                    q.push(newLocation);
                }
                newLocation = node*2;
                if(newLocation <= 100000 && newLocation >= 0 && !visited[newLocation]){
                    weight[newLocation] = weight[node] + 1;
                    visited[newLocation] = 1;
                    trace[newLocation] = node;
                    q.push(newLocation);
                }
    }
}
int main(void){
    int n, k;
    cin >> n >> k;
    if(n == k) cout << 0 << "\n" << n;
    else bfs(n, k);
}