[백준 12851]- 숨박꼭질2 (C++)[골드4]

📕문제

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

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

📗입력

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

📗출력

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

 

🔎문제 해석

문제를 읽어보면 동생을 찾을 수 있는 가장 빠른 방법을 요구한다. 
--> BFS 알고리즘을 사용해야 한다는 것을 여기서 유추해야 합니다.
3가지의 방법(+1,-1,*2)으로 계속 탐색해서 도착지에 도착하는지 검사하면 되는 문제입니다.

 

💡문제 풀이

• 이동 방법은 3가지입니다.
  • {좌표+1, 좌표 -1, 좌표 *2}이고 모두 소요시간은 1초로 동일합니다.
  • 우리는 현재 지역에서 갈 수 있는 3가지의 방법으로 탐색을 시작합니다.
• 방문 체크
  • 중복되는 작업을 피하기 위해서 방문처리를 해줘야 합니다.
    • 저는 그 지역을 방문했다면 그때의 시간을 기록해서, 큐에 넣기 전에 시간대를 계속 비교해서 
      시간이 더 짧은 시간에 방문했다면 큐에 넣고, 방문시간을 업데이트해줬습니다.
    • 만약 방문했는데, 기록된 시간보다 더 크다면, 굳이 큐에 넣어줄 필요가 없습니다.
• 도착 지점
  • 만약 도착지점에 도착했다면, 그때의 시간을 기록해줘야 합니다.
    • 문제에서 도착지점에 도착한 가장 빠른 시간대의 시간을 원하기 때문에, 계속 도착했다면 기록된 시간과 
      비교해 주는 작업을 해야 합니다.
  • 만약 탐색하려는 지역의 시간대가 , 기록된(도착지점) 시간대보다 크다면 검사할 필요가 없기 때문에 검사를 생략합니다.

 

❌주의할 점

해당 문제는 쉽지만, 좌표에 바운더리가 크기 때문에 최적화를 잘해줘야 합니다.
(저도 최적화 때문에 한번 틀린 경험이...)
최대한 탐색의 경우의 수를 줄여야 하기에, 방문체크, 도착 지점에 대한 시간대 기록을 해줬습니다.

 

💻코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <limits.h>
using namespace std;
int x, y;
queue<pair<int, int>> q;
void funct();
int ans = 0;
int mintime = INT_MAX;
int main()
{
    cin >> x >> y;
    q.push(make_pair(0, x)); // {시간, 좌표} -> 를 q에 넣음.
    funct();
    cout << mintime << "\n" << ans << endl;
}
void funct()
{
    vector<int> visit(1000001, INT_MAX); //시간대를 계속 최소값으로 업데이트 해주기 위한 초기값 설정
    visit[x] = 0;
    while (!q.empty())
    {
        int time = q.front().first;
        int location = q.front().second;
        q.pop();
        if (time > mintime){ //도착했을때의 시간대보다 길다면 검사를 생략
            break;
        }
        if (visit[location] < time){ //방문한 지역이 이미 방문했다면 == 시간대가 더 크다면 생략.
            continue;
        }
        visit[location] = time; //방문 처리. 시간대를 기록.
        if (location == y && time <= mintime){ // 처음으로 도착햇다면, 그때의 시간을 기록해두자.
            ans++;
            mintime = time;
            continue;
        }
        //아래 코드는 모두 이동하는 위치가 범위를 벗어나지 않고, 시간을 업데이트 해줄 필요성이 있을 때의 작업.
        if (location * 2 <= 100000 && visit[location * 2] >= time + 1){
            q.push(make_pair(time + 1, location * 2));
            visit[location * 2] = time + 1;
        }
        if (location - 1 >= 0 && visit[location - 1] >= time + 1){
            q.push(make_pair(time + 1, location - 1));
            visit[location - 1] = time + 1;
        }
        if (location + 1 <= 100000 && visit[location + 1] >= time + 1){
            q.push(make_pair(time + 1, location + 1));
            visit[location + 1] = time + 1;
        }
    }
}

 

😀느낀 점

• 처음에는 시간대를 하나하나 업데이트해주는 작업을 생략하기 위해서 우선순위 큐를 사용해서, 시간을 기준으로 정렬하는 작업을 했습니다.
  • 이렇게 되면 하나하나 시간대를 비교해 주는 작업을 안 해줘도 된다고 생각했는데, 시간초과라는...
  • 아마 그때 최적화를 덜 한 상태여서,, 그런 거 같기도 합니다. 우선순위큐를 사용해도 될 거 같습니다.
• 최적화 때문에 애를 좀 먹었습니다... 저는 4ms인데,, 생각보다 0ms인 분들도 많더라고요,, 자괴감이 드네