[백준 13549] - 숨박꼭질3(C++)

📕문제

---

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

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

📕입력

---

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

📕출력

---

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

 

🔎문제 해석

---

가장 빠르게 갈 수 있는 경로를 찾는 문제면 BFS를 이용해서 풀이하는 것이 일반적인 방법이다.

초기에는 priority_queue를 이용해서 문제를 풀 생각이었다.

pq에는 시간이 빠른 이동이 top에 가게끔 선언해줬다. 이렇게 설계하고 보니까 현재 위치에서 *2 값만이 계속 쭉쭉쭉 pq의 top에 위치해서 최대 이동거리까지 갱신이 안되어있어서, 이렇게 풀면 안 되나..?라고 생각했다.

그래서 pq의 정렬을 시간 순서가 아닌 도착지점과의 거리차로 정렬했는데,

이 방법도 적절한 정렬기준이 아니라고 판단했고 [도착지점의 도착하는 순간의 시간이 최소 시간이 아닌 경우가 있음]

시간이 오래걸리더라도 시간을 기준으로 정렬하는 것이 맞다고 판단하고 그렇게 풀었다.

• 초기 pq 정렬 기준  : 시간 오름차순
• 수정 pq 정렬 기준 : 현재 지점과 도착지점 까지의 거리 차이의 절대값을 기준으로 오름차순
• 최종 pq 정렬 기준 : 시간 오름차순

👀문제 풀이 방식

---

• pq 에는 {시간, 현재 지점} 을 넣어줬다.
• visit 배열을 선언해서 방문의 여부를 검사했다.
• bfs()를 하기전에 pq에 {0,n}을 푸쉬하고, visit[n]을 방문처리해줬다. 
• bfs()실행
  • 기본적인 알고리즘은 pq가 empty가 될때까지 반복하고 pq의 top에 해당하는 원소가 도착지점에 도착하면 return 해줬다.
  • 현재 pq에 top에 해당하는 지점을 방문처리해줬다.
  • 기본적인 이동은 현재지점에서 +1, -1 , *2가 있다.
  • 이동한 좌표가 방문을 하지 않은 상태고, 이동 좌표가 적절한 좌표라면 pq에 넣어줬다.
    • 이동이  +1, -1인 경우에는 기존 시간의 +1 값을 pq에 넣 어줬다. 
      • pq{time+1, location+1 or location-1}
    • 이동이 *2인 경우에는 기존 시간의 값을 pq에 넣어줬다. 
      • pq{time,location*2}

💻코드

/*
백준 골드5 숨박꼭질 13549
*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <math.h>
using namespace std;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
vector<int> visit;
int n, k, result = 0;
int bfs();
int main()
{
    cin >> n >> k; //좌표는 둘다 양수
    visit.resize(100001, 0);
    pq.push(make_pair(0, n));
    visit[n] = true;
    cout << bfs();
    //점프 2배, 이동 +-1
}
int bfs()
{

    while (!pq.empty())
    {
        int location = pq.top().second;
        int t = pq.top().first;
        visit[location] = 1;
        pq.pop();
        if (location == k)
        {
            return t;
        }
        if (visit[location + 1] == 0 && location + 1 < 100001)
        { //아직 방문안했고 유효한 좌표
            pq.push(make_pair(t + 1, location + 1));
        }
        if (visit[location - 1] == 0 && location - 1 >= 0)
        { //아직 방문안했고, 유효한 좌표
            pq.push(make_pair(t + 1, location - 1));
        }
        if (location * 2 < 100001 && visit[location * 2] == 0)
        { //아직 방문안했고, 유효한 좌표
            pq.push(make_pair(t, location * 2));
        }
    }
}

 

✔느낀점

• 초기에 pq의 기준을 잡을 때 굉장히 애를 먹었다.
• 그리고 pq에 방문한 동시에 방문처리를 해줘서 초기에 틀렸었는데, pq에 넣기만 하면 방문처리를 하면 안 된 것은 당연한 건데,, 살짝 어리석었네