[백준/Python] 1238번 파티 풀이

문제 해석

---

 

---

문제 풀이

---

이 문제는 벨만포드 풀이와 다익스트라 풀이가 있으며 다익스트라 2번 만으로도 풀어낼 수 있다.

벨만포드의 경우 C++에서는 통과하였으나 pypy, python 모두 불통과를 받았다...
모든 순서쌍의 거리를 계산하는 방식이니 아래 코드에서만 설명하고 생략하자

 

다익스트라 2회로 문제를 풀어낼 수 있다는 것이 너무나도 흥미로웠는데 이유는 아래와 같다.

모든 마을(노드)에서 특정 마을로 가는 길(간선)이 존재한다고 하면 간선을 뒤집어서 특정 마을에서 출발하면 모든 마을로 가는 최소 거리를 알 수 있다. (너무나도 충격적인 발상이다..... 대체 뭘 해야 이런 발상이 가능하지)

그리고 기존 순서쌍을 이용해 특정 마을에서 모든 간선으로 돌아가는 거리를 계산하면 총 2번만에 계산할 수 있다.

 

예시 그림자료

---

코   드

---

다익스트라 2회 코드 (python)

import sys
import heapq

N, M, X = map(int,sys.stdin.readline().split())
graph = [[] for _ in range(N+1)]
reverse_graph = [[] for _ in range(N+1)]

def find_path(sp, g):
    dist = [0x3f3f3f3f for _ in range(N+1)]
    pq = []
    heapq.heappush(pq, (sp, 0))
    while len(pq):
        ep, time = heapq.heappop(pq)
        for branch, t in g[ep]:
            if dist[branch] > time + t:
                dist[branch] = time + t
                heapq.heappush(pq, (branch, time + t))
        
    return dist

for _ in range(M):
    sp, ep, time = map(int,sys.stdin.readline().split())
    graph[sp].append((ep, time))
    reverse_graph[ep].append((sp, time))

fromX = find_path(X, graph)
toX = find_path(X, reverse_graph)

print(max([fromX[i] + toX[i] for i in range(1,N+1) if i != X]))

벨만-포드 코드 (C++)

#include <bits/stdc++.h>
using namespace std;
int answer, N, M, X;
vector< vector<int> > village;

int main() {
    ios::sync_with_stdio(0), cin.tie(0);    
    cin >> N >> M >> X;

    vector< vector<int> > village(N+1, vector<int>(N+1, 0));
    vector< vector<int> > dist(N+1,vector<int>(N+1, 0x3f3f3f3f));

    for (int i = 0 ; i < M ; i++) {
        int sp, ep, time;
        cin >> sp >> ep >> time;
        village[sp][ep] = time;
    }

    for(int i = 1 ; i <= N ; i++) {
        for (int j = 1 ; j <= N; j++) {
            if (i == j) dist[i][j] = 0;
            else if(village[i][j]) dist[i][j] = village[i][j];
            else dist[i][j] = 0x3f3f3f3f;
        }
    }

    for (int k = 1; k <= N; k++) {
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }

    for (int i = 1; i <= N ; i++) {
        answer = max(dist[i][X] + dist[X][i], answer);
    }
    cout << answer;
}

---

느낀점: 확실히 C++이 속도적 측면에서 장점이 있는 것 같다! 간선을 뒤집는 센스 다음에 써먹어야겠다.

링크: https://www.acmicpc.net/problem/1238

1238번: 파티