[백준] 13549 숨바꼭질 3

November 09, 2021 ( last updated : November 09, 2021 )
DP 알고리즘

https://github.com/sneakstarberry/

Abstract

[백준] 13549번 숨바꼭질 3

[백준] 13549번 숨바꼭질 3

백준 13549번

알고리즘 유형

풀이방법

BFS로 모든 경우의 수를 확인하면서 위치에 도달할 경우 리턴한다.

하지만 몇번을 갔는지가 아니라 시간이 얼마나 걸리는지가 중요하기 때문에 priority queue를 이용한다.

마이너스를 이용하면 자동으로 순서를 반대로 할 수 있을 줄 알았는데 잘안되서 그냥 greater를 이용해서 오름차순으로 정렬하였다.

#include <iostream>
#include <queue>
#include <vector>
#define MAX 100001
using namespace std;

int N, K;

int is_visited[MAX];
int main()
{
  cin >> N >> K;
  priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > q;

  q.push(make_pair(0, N));
  is_visited[N] = 1;
  while (!q.empty()) {
    pair<int,int> top = q.top();
    q.pop();

    if (top.second == K) {
      cout << top.first;
      return 0;
    }

    if (top.second * 2 < MAX && !is_visited[top.second*2]) {
      q.push(make_pair(top.first, top.second * 2));
      is_visited[top.second*2] = 1;
    }
    if(top.second + 1 < MAX && !is_visited[top.second + 1]) {
      q.push(make_pair(top.first + 1, top.second +1));
      is_visited[top.second + 1] = 1;
    }
    if(top.second - 1 >= 0 && !is_visited[top.second - 1]) {
      q.push(make_pair(top.first + 1, top.second - 1));
      is_visited[top.second - 1] = 1;
    }
    
  }
  
  return 0;
}

Originally published November 09, 2021
Latest update November 09, 2021

Related posts :

{# #}