[백준] 1697번 : 숨바꼭질 C++ 문제풀이 솔루션

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

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

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

예제 입력 1 복사

5 17

예제 출력 1 복사

4

힌트

수빈이가 5-10-9-18-17 순으로 가면 4초만에 동생을 찾을 수 있다.

 

 

 

거리배열을 따로 정의하여 while문의 반복 횟수와 상관없는 최단 거리를 구할 수 있습니다.

 

인접 리스트의 모든 요소를 큐에 삽입하며 진행하던 기본적인 bfs를 응용하여 현재거리의 x-1, x+1, x*2를 큐에 넣어줍니다.

#include <bits/stdc++.h>
#define fast_io cin.tie(NULL); ios_base::sync_with_stdio(false)
using namespace std;

int main() {
  fast_io;
  int n, m;
  cin >> n >> m;
  queue<int> q;
  vector<int> distance(max(n, m) + 2, 0);
  vector<bool> visited(max(n, m) + 2, true);
  q.push(n);
  visited[n] = false;
  while (!q.empty()) {
    int cur = q.front();
    if (cur == m) {
      cout << distance[cur];
      return 0;
    }
    q.pop();
    int a = cur * 2;
    int b = cur + 1;
    int c = cur - 1;
    if (a == m) {
      distance[a] = distance[cur] + 1;
      break;
    } else if (b == m) {
      distance[b] = distance[cur] + 1;
      break;
    } else if (c == m) {
      distance[c] = distance[cur] + 1;
      break;
    }
    if (a < m + 2 && visited[a]) {
      q.push(a);
      distance[a] = distance[cur] + 1;
      visited[a] = false;
    }
    if (b < m + 2 && visited[b]) {
      q.push(b);
      distance[b] = distance[cur] + 1;
      visited[b] = false;
    }
    if (visited[c]) {
      q.push(c);
      distance[c] = distance[cur] + 1;
      visited[c] = false;
    }
  }
  cout << *max_element(distance.begin(), distance.end());
  return 0;
}