[백준] 13913번: 숨바꼭질 4

문제

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

접근 방법

기존 숨바꼭질2 문제 + 추적

1. 인접리스트

처음에는 인접리스트를 이용해서 풀 수 있겠다고 생각하였으나
생각해보니 BFS를 이용해서 1번만 방문하기 때문에
인접리스트까지 이용하는 것은 비효율적이다.

2. 배열

이전 위치를 기록하는 배열 하나를 이용하여 역추적해나간다.

풀이

1. 인접리스트

#include <iostream>
#include <queue>
#include <vector>
#include <stack>

#define MAX 100000

using namespace std;

int N, K;

int visited[MAX+4];
vector<int> adj[MAX+4];


void Input()
{
    cin >> N >> K;
}

void Solve()
{
    // BFS 

    queue<int> q;
    q.push(N);
    visited[N] = 1;
    
    while(!q.empty())
    {
        int curr = q.front();
        q.pop();

        // 도착했을 경우
        if (curr == K)
            break;

        // 1초 후 이동 범위 
        for (int next : {curr-1, curr+1, curr*2})
        {
            // 범위 안에 있을 때
            if (0 <= next && next <= MAX)
            {
                // 방문하지 않았다면
                if (!visited[next])
                {
                    q.push(next); 
                    visited[next] = visited[curr] + 1; // 방문 처리
                    adj[next].push_back(curr); // 인접 리스트에 추가
                }
                
            }
        }
    }
    
    cout << visited[K] - 1 << '\n';


    // 도착 지점에서 역추적하면서 스택에 넣는다.

    int curr = K;

    stack<int> s;
    s.push(curr);

    while(curr != N)
    {
        for(int i : adj[curr])
        {   
            curr = i;
            s.push(curr);
        }
    }
    
    // 스택에서 꺼내어 출력한다.

    while(!s.empty())
    {
        cout << s.top() << " ";
        s.pop();
    }

}

int main()
{
    Input();
    Solve();

    return 0;
}

결과

2. 배열

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>

#define MAX 100000

using namespace std;

int N, K;

int visited[MAX+4];
int prevArr[MAX+4];


void Input()
{
    cin >> N >> K;
}

void Solve()
{
    // BFS 

    queue<int> q;
    q.push(N);
    visited[N] = 1;
    
    while(!q.empty())
    {
        int curr = q.front();
        q.pop();

        // 도착했을 경우
        if (curr == K)
            break;

        // 1초 후 이동 범위 
        for (int next : {curr-1, curr+1, curr*2})
        {
            // 범위 안에 있을 때
            if (0 <= next && next <= MAX)
            {
                // 방문하지 않았다면
                if (!visited[next])
                {
                    q.push(next); 
                    visited[next] = visited[curr] + 1; // 방문 처리
                    prevArr[next] = curr; // 이전 것을 등록하여 역추적 
                }
                
            }
        }
    }
    
    cout << visited[K] - 1 << '\n';


    // 도착 지점에서 역추적하면서 벡터에 넣는다.
    vector<int> v;

    for(int i = K; i != N; i = prevArr[i])
    {
        v.push_back(i);
    }
    v.push_back(N); // 시작 지점도 넣기

    // 거꾸로 뒤집기 
    reverse(v.begin(), v.end());

    for(int i : v) cout << i << " ";


}

int main()
{
    Input();
    Solve();

    return 0;
}

결과

정리

더 효율적으로 할 수 있게 생각하기!!