[백준] 1948: 임계 경로 (수정)

0. 문제 주소

 

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

1948번: 임계경로

 

 

1. 풀이

 

위상 정렬 문제들을 풀다 보면 흔히 볼 수 있는 description이 보인다. 실제로 위상 정렬로 풀고

 

[PS/ShortestPath] - [BOJ] 5719: 거의 최단 경로에서 쓰인 테크닉을 쓰면 원하는 edge의 개수를 구할 수 있다.

 

어렵지 않은 문제라 글을 안 쓰려다가, 다익스트라로도 풀어 보면서 문제점을 발견해서 포스팅을 하게 됐다.

 

지금까지는 다익스트라 알고리즘을 아래와 같이 구현했었다.

 

    while(!PQ.empty()){
        auto p = PQ.top();
        PQ.pop();
        int curr = p.second, curr_dist = p.first;
        if (visited[curr]) continue;
        visited[curr] = true;
        for (auto pp: graph[curr]){
            int next = pp.first, weight = pp.second;
            if (dist[next] > dist[curr] + weight){
                dist[next] = dist[curr] + weight;
                PQ.push(pii(dist[next], next));
            }
        }
    }

 

문제가 됐던 부분은 curr가 볼 필요가 있는지 여부를 판단하는 부분이었다.

 

다익스트라 알고리즘의 특성상 이번 노드를 최초로 방문했다는 것은

 

함께 붙어있는 curr_dist 값이 출발점에서 curr까지 도달할 수 있는 최단 거리라고 생각해서 이렇게 구현을 했었고,

 

실제로 지금까지는 아무 이상이 없었다.

 

도대체 어디가 틀린지 모르겠어서 구글링을 해보고 저 부분을 아래와 같이 바꿨더니 통과가 됐다.

 

    while(!PQ.empty()){
        auto p = PQ.top();
        PQ.pop();
        int curr = p.second, curr_dist = p.first;
        // 바뀐 부분
        if (dist[curr] < curr_dist) continue;
        // 바뀐 부분
        for (auto pp: graph[curr]){
            int next = pp.first, weight = pp.second;
            if (dist[next] > curr_dist + weight){
                dist[next] = curr_dist + weight;
                PQ.push(pii(dist[next], next));
            }
        }
    }

 

두 코드 차이점을 도저히 모르겠지만 일단.. 앞으로는 무조건 이렇게 하기로 했다 ㅠ

 

 

-------- 3/14 수정 --------

 

친절하신 분이 질문글에 답변을 달아 주셔서 이유를 알 수 있었다.

 

우선 반례는 아래와 같다.

 

 

문제는 이 문제가 "최장거리"를 구해야 하는 부분에서 발생했었다.

 

이를 처리하기 위해 모든 간선의 가중치를 음수로 바꿨고,

 

이 경우 내가 처음 구현했던 방식으로 - 한 번 PQ에서 꺼냈던 정점은 다시 볼 필요가 없는 방식 - 구현을 하면

 

반례가 생긴다.

 

맨 처음 노드 2와 3이 갱신되고, 다음 4가 갱신된다. 그 다음 2가 다시 갱신되어야 하는데, visited[2] = true이므로

 

갱신에 실패하게 된다.

 

가중치들이 모두 양수로 설정되어 있는 상태에서 다익스트라 알고리즘을 돌리면, 처음에 생각했던 대로

 

PQ의 특성에 의해 PQ에서 한 번 뽑은 정점은 다시 볼 필요가 없는 것이 맞다. 다른 정점을 거쳐 더 작은 dist를 만들어 낼 수가 없으니까.

 

하지만 가중치들이 음수일 경우 다르다. 다른 정점을 거치면 dist가 더 짧아질 수 있기 때문에

 

PQ에서 한 번 꺼낸 이후, 나중에 더 작은 dist를 가지는 경우가 PQ에 push 될 수 있다.

 

새로 배운 방법으로 하면 두 가지 경우를 모두 커버할 수 있기 때문에 이 방법으로 하는 것이 안전할 것 같다.

 

2. 풀이 코드

 

* 유의할 점

 

AC 코드

 

#include <iostream>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
#include <utility>

#define pii pair<int, int>
#define INF 1987654321
#define MAX 10005

using namespace std;

int N, M, S, E;
vector<pii> graph[MAX];
vector<pii> graph_rev[MAX];
int dist[MAX];
bool visited[MAX];
priority_queue<pii, vector<pii>, greater<pii>> PQ;

int main(){
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    #endif
    
    scanf("%d %d", &N, &M);
    int u, v, w;
    for (int i=0;i<M;i++){
        scanf("%d %d %d", &u, &v, &w);
        graph[u].push_back(pii(v, -w));
        graph_rev[v].push_back(pii(u, -w));
    }
    scanf("%d %d", &S, &E);
    
    fill(dist, dist+MAX, INF);
    dist[S] = 0;
    PQ.push(pii(0, S));
    while(!PQ.empty()){
        auto p = PQ.top();
        PQ.pop();
        int curr = p.second, curr_dist = p.first;
        if (dist[curr] < curr_dist) continue;
        for (auto pp: graph[curr]){
            int next = pp.first, weight = pp.second;
            if (dist[next] > curr_dist + weight){
                dist[next] = curr_dist + weight;
                PQ.push(pii(dist[next], next));
            }
        }
    }
    printf("%d\n", -dist[E]);
    
    int edge_cnt = 0;
    queue<int> Q;
//    memset(visited, 0, sizeof(visited));
    Q.push(E);
    visited[E] = true;
    while(!Q.empty()){
        int curr = Q.front();
        Q.pop();
        for (auto pp: graph_rev[curr]){
            int next = pp.first, weight = pp.second;
            if (dist[curr] - weight == dist[next]){
                edge_cnt++;
                if (!visited[next]){
                    Q.push(next);
                    visited[next] = true;
                }
            }
        }
    }
    printf("%d\n", edge_cnt);

    return 0;
}

 

 

 

WA 코드

 

#include <iostream>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
#include <utility>

#define pii pair<int, int>
#define INF 1987654321
#define MAX 10005

using namespace std;

int N, M, S, E;
vector<pii> graph[MAX];
vector<pii> graph_rev[MAX];
int dist[MAX];
bool visited[MAX];
priority_queue<pii, vector<pii>, greater<pii>> PQ;

int main(){
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    #endif
    
    scanf("%d %d", &N, &M);
    int u, v, w;
    for (int i=0;i<M;i++){
        scanf("%d %d %d", &u, &v, &w);
        graph[u].push_back(pii(v, -w));
        graph_rev[v].push_back(pii(u, -w));
    }
    scanf("%d %d", &S, &E);
    
    fill(dist, dist+MAX, INF);
    dist[S] = 0;
    PQ.push(pii(0, S));
    while(!PQ.empty()){
        auto p = PQ.top();
        PQ.pop();
        int curr = p.second, curr_dist = p.first;
        if (visited[curr]) continue;
        visited[curr] = true;
        for (auto pp: graph[curr]){
            int next = pp.first, weight = pp.second;
            if (dist[next] > dist[curr] + weight){
                dist[next] = dist[curr] + weight;
                PQ.push(pii(dist[next], next));
            }
        }
    }
    printf("%d\n", -dist[E]);
    
    int edge_cnt = 0;
    queue<int> Q;
    memset(visited, 0, sizeof(visited));
    Q.push(E);
    visited[E] = true;
    while(!Q.empty()){
        int curr = Q.front();
        Q.pop();
        for (auto pp: graph_rev[curr]){
            int next = pp.first, weight = pp.second;
            if (dist[curr] - weight == dist[next]){
                edge_cnt++;
                if (!visited[next]){
                    Q.push(next);
                    visited[next] = true;
                }
            }
        }
    }
    printf("%d\n", edge_cnt);

    return 0;
}