[BOJ/13549/C++] 숨바꼭질 3

출처:https://www.acmicpc.net/problem/13549

문제

• 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

조건

• 수빈이는 걷거나 순간이동을 할 수 있다.
• 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. .
• 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다.

풀이

2가지의 가중치를 가지는 문제이다. 0 -1 BFS로 우선순위가 높은 친구를 앞에 넣어줌으로써 해결가능하다.

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
#define MAX_SIZE 100001
using namespace std;

int N, K;
int dist[MAX_SIZE];

void bfs()
{
  deque<int> dq;
  dq.push_back(N);
  dist[N] = 1;
  while (!dq.empty())
  {
    int cur = dq.front();
    dq.pop_front();

    if (cur == K)
      return;
    //*2 로 가는건 횟수가 0이므로, 걷는것 보다 먼저해주자.
    if (2 * cur < MAX_SIZE && !dist[2 * cur])
    {
      dq.push_front(2 * cur);
      dist[2 * cur] = dist[cur];
    }
    // +1,-1은 뒷쪽
    if (cur + 1 < MAX_SIZE && !dist[cur + 1])
    {
      dq.push_back(cur + 1);
      dist[cur + 1] = dist[cur] + 1;
    }
    if (cur - 1 >= 0 && !dist[cur - 1])
    {
      dq.push_back(cur - 1);
      dist[cur - 1] = dist[cur] + 1;
    }
  }
}

int main()
{
  cin >> N >> K;
  bfs();
  cout << dist[K] - 1 << '\n';
  return 0;
}