baekjoon 13549:숨바꼭질 3

baekjoon 13549 숨바꼭질 3

13549번 숨바꼭질 3

접근

저번에 숨바꼭질 1을 풀었을 땐 단순 bfs로 풀어냈다. 그리고 visited를 이용해서 이미 방문한 것들은 방문하지 않았다. 이렇게 할 수 있었던 이유는 queue순서가 시간 순서였다. 하지만 이번에는 순간이동 때문이 그렇지 않다.
일단 pair을 priority_queue에 넣을 것이고 시간을 first에 넣어서 시간이 적은 순으로 뽑을 것이다.
그리고 한번 뽑았을 때 먼저 순간이동들을 다 따진다. 그다음 +1, -1 이동들을 따진다.
이번에는 늦게 접근 하는 경로가 시간은 더 빠른 경우들이 가능하기 때문에 cache를 이용해서 새로 접근한 방식의 시간이
미리 저장된 것보다 적어야만 접근하고 queue에 넣는다.

코드

#include <iostream>
#include <queue>
#include <array>
using namespace std;
#define MAX 1e9
array<int, 100001> cache{};
int main(){
  int n, k; cin >> n >> k;
  if(n == k) {
    cout << 0; return 0;
  }
  fill(cache.begin(), cache.end(), MAX);
  priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
  q.push({0, n});
  while(!q.empty()){
    pair<int, int> cur = q.top(); q.pop();
    int next = cur.second;
    while(true){
      if(next == 0) break;
      next = next * 2;
      if(next > 100000) break;
      if(cache[next] <= cur.first){
        continue;
      }
      q.push({cur.first, next});
      cache[next] = cur.first;
    }
    if(cur.second-1 >= 0 && cache[cur.second-1] > cur.first+1){
      q.push({cur.first+1, cur.second-1});
      cache[cur.second-1] = cur.first+1;
    }
    if(cur.second+1 <= 100000 && cache[cur.second+1] > cur.first+1){
      q.push({cur.first+1, cur.second+1});
      cache[cur.second+1] = cur.first+1;
    }
    
  }
  cout << cache[k];
  

  return 0;
}
  
}

배운 점

bfs응용, 중복이 queue에 많이 들어가서 고생했다.