[2] [Class 3] - 백준 1697 숨바꼭질

www.acmicpc.net/problem/1697

1697번: 숨바꼭질

 

해당 지점으로 이동하는 규칙이 있고

여러 방법중 가장 빠른 방법의 횟수를 구하는 것이 목표인데요

모든 케이스를 조사하는 것 보단, 가장 빨리 결과가 등장하는 경우를 찾는것이 가장 적합해 보입니다.

이럴 땐 역시 BFS만한 것이 없다고 생각합니다. 

 

하나 찾으면 while문 벗어나서 출력하게끔 구성하였습니다. 

 

// BFS

#include <bits/stdc++.h>

using namespace std;

bool visited[100001];
int N,K;

int main(){
  ios_base :: sync_with_stdio(false); 
  cin.tie(NULL);

  cin >> N >> K;

  queue<pair<int,int> > q;

  q.push(make_pair(N, 0));
  vector<int> res;

  while(!q.empty()){
    pair<int,int> item = q.front();
    q.pop();

    if(visited[item.first]) continue;

    visited[item.first] = true;

    if(item.first == K){
      res.push_back(item.second);
      break;
    }

    if(item.first > 0){
      q.push(make_pair(item.first - 1, item.second + 1));
    }

    if(item.first + 1 <= 100000){
      q.push(make_pair(item.first + 1, item.second + 1));
    }

    if(item.first * 2 <= 100000){
      q.push(make_pair(item.first * 2, item.second + 1));
    }
  }

  sort(res.begin(), res.end(), less<int>());
  cout << res[0];

  return 0;
}