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

13549번: 숨바꼭질 3

 

문제

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

13549번: 숨바꼭질 3

 

 

풀이

다른 숨바꼭질 문제처럼 너비 우선 탐색(BFS)으로 해결할 수 있다. 단, x*2는 0초이므로 가장 우선적으로 해줘야 한다. 그리고 x+1과 x-1도 같은 1초가 걸리지만 뒤로 갔다가 ×2 하는 게 더 시간이 적게 걸릴 것이므로 x-1가 x+1보다 우선순위가 높다.

 

visited 배열을 -1로 초기화해주고 시작지점을 0으로 바꿔줬다. 이후 x*2, x-1, x+1을 차례로 돌면서 범위 내인 경우 x*2인 경우만 visited[x*2] = visited[x]로 해주고 나머진 이외엔 전 방문에서 +1 해준다.

 

그리고 처음으로 K에 도착하면 최단 시간을 구했으므로 BFS를 멈춰준다.

 

 

코드

#include <bits/stdc++.h>
using namespace std;

int n, k;
vector<int> visited(100001, -1);

void bfs(int s) {
  queue<int> q;
  q.push(s);
  visited[s] = 0;
  while (!q.empty()) {
    int x = q.front();
    if (x == k)
      return;
    q.pop();
    if (x * 2 <= 100000 && visited[x * 2] == -1) {
      q.push(x * 2);
      visited[x * 2] = visited[x];
    }
    if (x - 1 >= 0 && visited[x - 1] == -1) {
      q.push(x - 1);
      visited[x - 1] = visited[x] + 1;
    }
    if (x + 1 <= 100000 && visited[x + 1] == -1) {
      q.push(x + 1);
      visited[x + 1] = visited[x] + 1;
    }
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> n >> k;
  bfs(n);
  cout << visited[k] << '\n';
  return 0;
}