백준 알고리즘 13549번 : 숨바꼭질 3

링크

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

문제

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

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

입력

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

출력

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

예제 입력 및 출력

풀이법

풀다가 문제의 유형이 기존에 풀었던 숨바꼭질 문제들과는 다르길레 답지를 보고 풀었다.
이 문제의 핵심은 현재 위치를 x라고 할 때 +1,-1은 1초가 소요되지만 순간이동을 했을 때는 0초가 소요된다는 게 핵심이다.
즉, 순간이동의 우선순위가 더 높다는 것이고 우선순위 큐 또는 덱을 사용해서 풀 수 있다.
나는 덱을 사용해서 문제를 풀었고 현재 위치(cur)에서 +1,-1은 순간이동보단 우선순위가 낮으므로 덱의 뒤에다 넣어주었고, 순간이동은 우선순위가 높으므로 덱의 앞에다 넣어주었다.

풀이 코드(C++)

#include <iostream>
#include <deque>
#include <vector>
#include <queue>
#include <deque>
#include <algorithm> 
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define ffor(i, x) for (int (i) = 0; (i) < (x) ; ++(i))
#define coutln(x) cout << x << '\n'
#define MAX 100000
using namespace std;

bool vist[MAX];
int k,n;
deque<pair<int,int> > DQ; // <시간,노드> 순
int ans;

void bfs(int start){
  DQ.push_back({0,start});
  while(!DQ.empty()){
    int cur = DQ.front().second;
    int time = DQ.front().first;
    DQ.pop_front();
    vist[cur] = true;
    if(cur == k){
      ans = time;
      return;
    }
    if(cur - 1 >= 0 && !vist[cur - 1]){
      DQ.push_back({time + 1,cur - 1});
    }
    if(cur + 1 <= MAX && !vist[cur + 1]){
      DQ.push_back({time + 1, cur + 1});
    }
    // 우선순위가 높으므로 앞쪽에 넣어줌
    if(2*cur <= MAX && !vist[2*cur]){
      DQ.push_front({time, 2*cur});
    }
  }
}

int main(){
  fastio;
  cin >> n >> k;
  bfs(n);
  printf("%d\n",ans);
  return 0;
}

재풀이 (2021-11-03)

#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#define X first
#define Y second
#define pb push_back
#define fastio cin.tie(0)->sync_with_stdio(0)
#define sz(v) (int)(v).size()
#define all(v) v.begin(), v.end()
#define rall(v) (v).rbegin(), (v).rend()
#define compress(v) sort(all(v)), (v).erase(unique(all(v)), (v).end())
#define OOB(x, y) ((x) < 0 || (x) >= n || (y) < 0 || (y) >= m)
#define debug(x) cout << (#x) << ": " << (x) << '\n'
using namespace std;
using ll = long long;
using ull = unsigned long long;
using dbl = double;
using ldb = long double;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vi = vector<int>;
using vs = vector<string>;
using tii = tuple<int,int,int>;
template<typename T> using wector = vector<vector<T>>;

const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;
const ll LNF = 1e18 + 7;

int main() {
  fastio;
  int n,k; cin >> n >> k;
  vi dist(100'001, -1);
  deque<int> DQ;
  dist[n] = 0;
  DQ.push_back(n);
  while(!DQ.empty()){
    auto cur = DQ.front(); DQ.pop_front();
    if(cur == k) break;
    if(2 * cur <= 100000 && dist[2 * cur] == -1){
      DQ.push_front(2 * cur);
      dist[2 * cur] = dist[cur];
    }
    if(cur - 1 >= 0 && dist[cur - 1] == -1){
      DQ.push_back(cur - 1);
      dist[cur - 1] = dist[cur] + 1;
    }
    if(cur + 1 <= 100000 && dist[cur + 1] == -1){
      DQ.push_back(cur + 1);
      dist[cur + 1] = dist[cur] + 1;
    }
  }
  cout << dist[k] << "\n";
  return 0;
}

배운점

BFS에서의 우선순위 판별법