[백준] 13549 숨바꼭질 3 dijkstra

문제 :

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

13549번: 숨바꼭질 3

 

풀이 :

숨바꼭질1 문제와 달리 이벤에는 순간이동(M x 2)시 시간은 0초라는 조건이 다르다. 즉 걷기(M-1, M+1) 조건시의 가중치와 순간이동의 가중치가 달라 최소 시간을 구하기 위해선 순간이동이 우선시 되어야 했고

거리가 작은순으로 정렬해주는 우선순위큐를 사용해 다익스크라를 적용했다.

가지 않았던 위치거나 또는 전에 갔을때의 시간보다 더 적게 걸리는 시간이 있다면 그 시간값으로 d 배열을 업데이트 해주어 최소 시간(비용)을 찾았다.

 

c++ 코드 :

//
//  13549_hide_seek3.cpp
//  SOMA👩🏻‍💻
//
//  Created by JoSoJeong on 2022/02/17.
//


#include <iostream>
#include <queue>
#include <string.h>

using namespace std;
int N, K;
int moving[3] = { - 1, 1, 2}; //walk, jump

int d[100001]; // 최단 시간 테이블
int n_now; // 다음 위치
int n_t; // 다음 위치시의 시간

void hide_seek_minTime() {
    priority_queue<pair<int, int>> pq; //시간, 위치
    pq.push({0, N});
    d[N] = 0;
    
    while(!pq.empty()){
        int t = -pq.top().first;
        int now = pq.top().second;
        pq.pop();
        
        for(int i = 0; i < 3; i++){
            if(i == 2) {
                n_now = moving[i] * now;
                n_t = t;
            }else {
                n_now = moving[i] + now;
                n_t = t + 1;
            }
            
            if(n_now < 0 || n_now > 100000) continue; // 범위
            
            if(d[n_now] == -1 || d[n_now] > n_t) { // 가지 않은 길 or 더 시간 적다면
                d[n_now] = n_t;
                pq.push({-n_t, n_now});
            }
        }
        
    }
    
}

int main(){
    cin >> N >> K;
    memset(d, -1, sizeof(d));
    
    hide_seek_minTime();
    cout << d[K] << '\n'; // K위치까지 업데이트된 시간
    return 0;
}

 

 

 

참고 :

https://excited-hyun.tistory.com/33