알고리즘 :: 백준 :: BFS :: 13549 :: 숨바꼭질3

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다.
수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

문제접근

• BFS에 대한 정의를 다시 생각해보자.
  1. BFS는 queue를 이용해서 최단 거리를 구할 수 있다.
  2. BFS는 모든 간선의 가중치가 1일 때 사용할 수 있다.
  3. 이때 가중치는 문제에서 구하고자 하는 값과 동일한 특성을 가져야 한다.
     • e.g. 문제에서 '거리'를 구하려고 하면 가중치는 '거리' 여야 한다.
• 그럼, 만일 간선의 가중치가 1이 아닐 때는 어떨까?
  
• 수빈이는 x점에 있을 때, 1초를 소요해서 앞으로 한 칸, 뒤로 한 칸 갈 수 있고 또는 바로 2x점으로 순간이동 할 수 있다. 따라서 간선의 가중치가 1로 동일하다고 할 수 없다.
• 이런 경우에 BFS를 사용하는 방법은 두 가지다.
  1. DP에서 우리는 문제에 주어진 조건에 따라 1차원 메모이제이션 뿐만 아니라 2차원, 3차원 메모이제이션도 사용했다. 이를 이용해서 정점을 나타내는 방법을 차원을 다르게 해서 표현하는 방법이 있다. 이 방법을 사용하면 모든 간선의 가중치를 1로 만들 수 있다.
  2. 다중 queue를 사용할 수 있다. 예를 들어, 0인 간선을 저장하는 큐, 1인 간선을 저장하는 큐, 2인 간선을 저장하는 큐 등으로 여러 큐를 만든 다음 원하는 곳에 push-pop 하도록 구현해서 가중치를 1로 만들 수 있다.
     • 특히, 본 문제처럼 간선의 가중치가 두 가지인 문제를 0, 1 BFS라고 부르며, deque을 이용해서 구현한다.
• 1초가 소요되는 두 가지 이동의 경우 push_back()으로 정점을 뒤로 넣어준다.
  0초가 소요되는 순간이동의 경우 push_front()로 정점을 앞으로 넣어준다.

코드

#include <iostream>
#include <algorithm>
#include <deque>
using namespace std;

int n, k, ans = INT32_MAX;
bool visited[100001];

int main(){
    cin >> n >> k;

    deque<pair<int,int>> q;
    q.push_back(make_pair(n,0));

    while(!q.empty()){
        int pos = q.front().first, t = q.front().second;
        int goPos = pos + 1, backPos = pos - 1, telePos = 2 * pos;
        q.pop_front();
        
        if(pos == k) ans = min(ans, t);
        
        if(telePos <= 100001 && !visited[telePos]){
            visited[telePos] = true;
            q.push_front({telePos, t});
        }
        if(backPos >= 0 && !visited[backPos]){
            visited[backPos] = true;
            q.push_back(make_pair(backPos, t + 1));
        }
        if(goPos <= 100001 && !visited[goPos]){
            visited[goPos] = true;
            q.push_back(make_pair(goPos, t + 1));
        }
    }
    cout << ans << '\n';
}

결과