[백준 / BOJ] C++ 12851 숨바꼭질 2

12851번: 숨바꼭질 2

 

문제

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

12851번: 숨바꼭질 2

 

 

풀이

BFS로 풀었다. 큐에는 pair로 좌표와 걸린 시간을 넣어줬다. 처음으로 K위치에 도달한 경우, m을 걸린 시간으로 할당하고 cnt++ 해준다. BFS 특성상 이후 다시 K에 도달하는 경우는 반드시 걸린 시간이 같거나 길 수밖에 없다. 따라서 K에 도달할 때마다 cnt++ 해주고 처음으로 더 긴 시간이 되면 BFS를 탈출한다.

 

 

코드

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

int n, k, cnt = 0, m = 2147483647;
vector<int> visited(100001, 0);

void bfs(int xx) {
  queue<pair<int, int>> q;
  q.push({xx, 0});
  visited[xx] = 1;
  while (!q.empty()) {
    int x = q.front().first;
    int y = q.front().second;
    visited[x] = 1;
    q.pop();
    if (m < y)
      break;
    if (x == k) {
      m = y;
      cnt++;
    }
    if (x + 1 >= 0 && x + 1 <= 100000)
      if (!visited[x + 1])
        q.push({x + 1, y + 1});
    if (x - 1 >= 0 && x - 1 <= 100000)
      if (!visited[x - 1])
        q.push({x - 1, y + 1});
    if (x * 2 >= 0 && x * 2 <= 100000)
      if (!visited[x * 2])
        q.push({x * 2, y + 1});
  }
}

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