백준 13549 숨바꼭질 3

 

 

아이디어

• 0-1 BFS 사용해서 동생위치 찾음
  • 처음 좌표 넣을떄 2의배수 모두 추가
  • 중간에 x2배(시간이 0) 다른것보다 먼저 수행해줘야함
  • priority_queue 사용해서 수행

 

시간복잡도 계산

• 우선순위 큐 사용 : O(NlgN) = 1e5 * 20
• BFS : O(V+E)
  • 노드 개수 : N
  • 간선 개수 : 최대 N
  • O(N)
• 총합 : O(NlgN + N) : O(NlgN) > 가능

인트 계산

• 가장 빠른시간 최대 1e5 > INT 가능

 

코드

#include <iostream>
#include <queue>
 
using namespace std;
typedef pair<int, int> pi2;
 
bool chk[100010];
int main() {
    int N,K; cin >> N >> K;
    
    priority_queue<pi2, vector<pi2>, greater<pi2>> pq;
    // 시작값 큐에 넣어줌, 앞에는 시간, 뒤에는 노드
    pq.push(make_pair(0,N));
    fill(chk, chk+100010, 0);
    chk[N] = 1;
    if(N==K) {
        cout << 0 << '\n';
        return 0;
    }
    
    while(!pq.empty()) {
        int et = pq.top().first;
        int en = pq.top().second;
        pq.pop();
        
        if(en == K) {
            cout << et << '\n';
            return 0;
        }
        
        // 2배 먼저 해주기
        int en2 = en * 2;
        while(en2 <= 100000) {
            if(chk[en2]) break;
            
            chk[en2] = 1;
            pq.push(make_pair(et, en2));
            en2 = en2 * 2;
        }
        
        // 1더한것
        if(en+1 <= 100000) {
            if(chk[en+1] == false) {
                chk[en+1] = 1;
                pq.push(make_pair(et+1, en+1));
            }
            
        }
        
        
        // 1뺀것
        if(en-1 >= 0) {
            if(chk[en-1] == false) {
                chk[en-1] = 1;
                pq.push(make_pair(et+1, en-1));
            }
            
        }
    }
    return 0;
}
 

 

문제유형

• BFS - 0/1 : 다른 노드보다 우선 수행해줘야하는 조건이 있을때 사용