[algorithm] 숨바꼭질 3

가중치가 같을 경우 bfs로 하면 최단거리가 나오지만,
가중치가 다를 경우 dijkstra를 통해 최단거리를 구해야한다.

 

 

이 문제는 자칫 보면 조건문의 순서로 문제가 맞고 틀리고가 결정되는 것처럼 보일 수 있다.
나도 이 문제를 풀 때 실수를 했다.

#include <iostream>
#include <vector>
#include <functional>
#include <queue>
using namespace std;

bool visited[100001] = {false};
int directx[] = {1, -1, 2};
int dijkstra(int soobin, int sister){
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
    pq.push({0, soobin});
    visited[soobin] = true;

    while(!pq.empty()){
        pair<int,int> node = pq.top();
        pq.pop();
        if(node.second == sister){
            return node.first;
        }
         for(int i = 0; i < 3; i++){
            int dx, thisWeight;
            if(i != 0) {
                dx = node.second + directx[i];
                thisWeight = node.first + 1;
            }
            else{ 
                dx = node.second * directx[i];
                thisWeight = node.first;
            }
            if(dx >= 0 && dx <= 100000 && !visited[dx]){
                visited[dx] = true;
                pq.push({thisWeight, dx});
            }
        }
    }
}
int main(void){
    int soobin, sister;
    cin >> soobin >> sister;
    cout << dijkstra(soobin, sister);
}

 

위의 코드는 틀린 코드이고,

directx[] 배열의 값을 {2, 1, -1} 로 바꾸었더니 맞았다.

왜 맞을까?

백준의 질문 검색을 뒤져보던 중 알게되었다..

 

 +1이나 -1 로 먼저 뒤쪽에 집어넣게 되어 visited 가 true 가 된 숫자는
이미 visited가 true 이기 때문에 *2로 앞쪽에 집어넣어지지 않습니다.

이런 이유로 visited가 true였기 때문에 weight는 갱신되지 않았고, 그래서 계속 틀렸던 것이었다.

참고로 *2의 경우 weight가 0에 해당하니까 갱신되어야만 하는 것이고
만약 weight가 1보다 높은 수였다면 갱신될 필요가 없다.

#include <iostream>
#include <vector>
#include <functional>
#include <queue>
using namespace std;

bool visited[100001] = {false};
int directx[] = {1, -1, 2};
int dijkstra(int soobin, int sister){
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
    pq.push({0, soobin});
    visited[soobin] = true;

    while(!pq.empty()){
        pair<int,int> node = pq.top();
        pq.pop();
        if(node.second == sister){
            return node.first;
        }
        visited[node.second] = true;
         for(int i = 0; i < 3; i++){
            int dx, thisWeight;
            if(i != 0) {
                dx = node.second + directx[i];
                thisWeight = node.first + 1;
            }
            else{ 
                dx = node.second * directx[i];
                thisWeight = node.first;
            }
            if(dx >= 0 && dx <= 100000 && !visited[dx]){
                pq.push({thisWeight, dx});
            }
        }
    }
}
int main(void){
    int soobin, sister;
    cin >> soobin >> sister;
    cout << dijkstra(soobin, sister);
}

if문에 존재하는 visited위치를 상단으로 올리게 되어도 맞는다.

그렇지만 이 경우, 계속적인 갱신이 되므로 맨위의 코드가 더 빠른 속도로 해결된다.