[백준] 1697번 숨바꼭질 c++

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

1697번: 숨바꼭질

문제

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

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

입력

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

출력

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

 

 

접근방식

수빈이의 이동 가능 방식이 -1, *2, +1 3가지 이므로 BFS를 활용해서 탐색을 진행하여 해를 구할 수 있다.

 

고려해야할 사항

- -1 이동 시 좌표가 음수가 되서는 안된다.

- +1와 *2이동 시 좌표가 100000이 넘어서는 안된다.

- depth가 깊어질 수 록 3^n만큼 기하급수적으로 늘어난다. 방문체크 배열을 사용하여 이를 해결한다.

- 어디까지가 1번의 이동인지 판단해야 한다.

1) start값을 q에 넣은 후 -1의 값을 갖는 key을 queue에 넣는다.

2)꺼낸 q의 값이 -1일때가 한번 이동을 마친 경우이므로 이때 횟수를 카운팅 해준다.

 

#include <iostream>
#include <queue>
#include <cmath>

using namespace std;

int x,y;
queue<int> q;
int v[100001]={0};

int bfs(int start){
  if(start==y) return 0;
  int key=-1, result=0;
  q.push(start);
  q.push(key);
  v[start]=1;

  while(!q.empty()){
    int x = q.front();
    q.pop();

    if(x == y)
      return result;

    if(x!=key){
      if(x-1 >= 0 && v[x-1]==0){
        q.push(x-1);
        v[x-1]=1;
      }
      if(x*2 <= 100000 && v[x*2]==0){
        q.push(x*2);
        v[x*2]=1;
      }
      if(x+1 <= 100000 && v[x+1]==0){
        q.push(x+1);
        v[x+1]=1;
      }
    }
    else{
      q.push(key);
      result++;
    }
  }
  return result;
}

int main(){
  cin >> x >> y;
  cout << bfs(x) << "\n";
  return 0;
}