[Algorithm]Baekjoon 13913번 : 숨바꼭질4

https://www.acmicpc.net/problem/13913

13913번: 숨바꼭질 4

struct Node
{
    int pos;
 
    Node(int _pos) : pos(_pos){};
};
 
pair<int, int> visited[100001];
vector<int> result;
int start;
int dest;
 
void FindRoot(int n)
{
    result.push_back(n);
 
    if (n != start)
    {
        FindRoot(visited[n].second);
    }
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> start >> dest;
 
    int answer = 0;
    memset(visited, 0x3f, sizeof(visited));
 
    queue<Node> q;
    q.push(Node(start));
    visited[start] = { 0,start };
    int lastPos = 0;
 
    while (!q.empty())
    {
        Node curNode = q.front();
        q.pop();
 
        int curPos = curNode.pos;
 
        if (curPos == dest)
        {
            break;
        }
 
        int np1 = curPos * 2;
        int np2 = curPos + 1;
        int np3 = curPos - 1;
 
        if (np1 <= 100000 && visited[curPos].first + 1 <= visited[np1].first)
        {
            visited[np1].first = visited[curPos].first + 1;
            visited[np1].second = curPos;
            q.push(Node(np1));
        }
 
        if (np2 <= 100000 && visited[curPos].first + 1 <= visited[np2].first)
        {
            visited[np2].first = visited[curPos].first + 1;
            visited[np2].second = curPos;
            q.push(Node(np2));
        }
 
        if (np3 >= 0 && visited[curPos].first + 1 <= visited[np3].first)
        {
            visited[np3].first = visited[curPos].first + 1;
            visited[np3].second = curPos;
            q.push(Node(np3));
        }
    }
 
    cout << visited[dest].first << endl;
    FindRoot(dest);
    reverse(result.begin(), result.end());
 
    for (auto temp : result)
    {
        cout << temp << ' ';
    }
}

visited배열을 int에서 pair<int,int>로 바꿨다. pair의 first에는 기존대로 time(가중치값)을 넣고, second에는 해당 time을 넣을때의 curPos값, 즉 부모노드의 pos값을 넣었다. 

다익스트라처럼 비교를 통해 최소값일때만 값을 기록하고 큐에 넣기때문에 최종적으로 목표지의 부모노드를 타고 올라가면 그게 최단루트가 된다. 그걸 역순으로 출력하면 된다.