백준, BOJ, 13549번, 숨바꼭질 3 : C++ [CPP]

음.. 처음 생각하기 정말 어려웠다.

어떻게 BFS로 푼다는 거지..?

BFS는 모든 단계 탐색이 비용이 같아야하는데.. 쟤는 0초인데??

우선순위 큐를 쓰라는 말을 들어도 못알아듣다가 다른 분의 코드를 조금 보고나서야 알았다.

 

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

 

---

 

#맞은 풀이

#include <bits/stdc++.h>

using namespace std;


int N, K;
bool visited[100002];

int main(){
    cin >> N >> K;
    
    //왜 우선순위 큐를 사용해야하느냐??
    //+1,-1의 노드를 탐색하는 것과 *2 노드를 탐색하는 것은 다르다.
    //즉, *2를 하는 것은 할 수 있는 만큼 하고 +1과 -1을 해야한다.
    //즉, 단계도 단계지만 시간으로 구분되어야 한다.
    
    //경과 시간, 위치 순임 (시간이 작은 순으로 탐색해야함)
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
    
    int ans = 0;
    

    //0초일 때 위치
    q.push({0,N});
    visited[N] = true;
    
    while(!q.empty()){
        auto cur = q.top();
        q.pop();
        
        if(cur.second == K){
            ans = cur.first;
            break;
        }
        
        for(int dir = 0; dir<3; dir++){
            int nx = 0;
            if(dir == 0){
                nx = cur.second * 2;
            }else if(dir == 1){
                nx = cur.second + 1;
            }else if(dir == 2){
                nx = cur.second - 1;
            }
            
            if(nx<0 || nx > 100000)continue;
            if(visited[nx]  == true)continue;
            
            if(dir == 0){
                q.push({cur.first, nx});
                visited[nx] = true;
            }else{
                q.push({cur.first + 1, nx});
                visited[nx] = true;
            }
        }
        
    }
    
    cout << ans;
    
    return 0;
}

 

생각하기가 어려웠다.

생각만하면 된다고 하지만

생각하기가 어려웠다.