[Python 3] BOJ - 1238 "파티"

 # 문제 링크 : https://www.acmicpc.net/problem/1238

1238번: 파티

 # 풀이 : 

개인적으로 이 문제는 인접리스트와 역인접 리스트를 만드는 것이라 생각한다. 정점의 갯수가 1000개 이하이기 때문에 O(N^3)인 벨만 포드를 실행해도 시간안에는 들어올 수 있으나 그것보다 인접리스트와 역인접리스트를 만들어서 파티가 일어나는 장소를 기준으로 다익스트라를 2번만 실행하는것이 더 효율적이다.

<그림 1. 문제 TC>

 위 그림1은 2번 정점에서 파티가 발생하는 것을 가정한 경우이다. 일반적인 다익스트라에 따라 2번 정점에서 실행하면 배열 D는 [1, 0, 5, 9]이다. 즉, 2번 정점에서 1번 정점으로 가는 최소 거리는 1, 2번 정점에서 3번 정점으로 가는 최소 거리는 5, 2번 정점에서 4번 정점으로 가는 최소 거리는 9이다. 그러나 이는 문제에서 요구하는 'X에서 집으로 돌아오는' 경우에 속하므로 '집에서 X로 가는' 경우도 구해야 정답을 올바르게 구할 수 있다.

 우선 역인접리스트를 만들기 전에, 1번 정점, 3번 정점, 4번 정점에 대해 다익스트라를 실행하면 각각 배열 D1은 [0, 4, 2, 7]이고 D3은 [2, 6, 0, 4]이고 D4는 [4, 3, 6, 0]이다. 따라서 1번 정점에서 2번 정점으로 가는 최소 거리는 4, 3번 정점에서 2번 정점으로 가는 최소 거리는 6, 4번 정점에서 2번 정점으로 가는 최소 거리는 3이다. 따라서 역인접 리스트를 통해 나온 R2가 [4, 0, 6, 3]이 보장된다면 파티가 일어나는 점을 제외한 나머지 정점들에 대해 N - 1번의 다익스트라를 실행하지 않고도 파티가 일어나는 점에 대해 1번의 다익스트라를 통해 '집에서 X로 가는 경우'를 구할 수 있다.

<그림 2. 역인접리스트>

 현재 문제에서 단방향 그래프임을 명시했으므로 일반적인 인접행렬의 경우, adj[시작 정점][끝 정점] = 비용이다. 그런데, 역인접 리스트에서는 n_adj[끝 정점][시작 정점] = 비용이다. 왜냐하면, 실제적으로는 시작정점에서 출발하여 끝정점으로 비용만큼의 시간이 걸려서 실제로 이동하는 것이만, 개념적으로 생각해보면 끝 정점에서 출발하여 시작정점으로 가는 비용이나 시작정점에서 끝 정점으로 가는 비용은 동일하기 때문이다. 다만, 끝 정점에서 시작정점으로 가는 경우는 실제로 갈 수 없기에 마치, 그림1과 그림2는 엄연히 다른 그래프인것 처럼 사실상 역인접리스트를 통해 원래의 그래프와 다른 그래프를 만들어서 '집에서 X로 가는 경우'를 구하는 것이라 생각하면 된다. 즉, 그림 1에서 정점 2에서 출발하는 간선들은 모두 지우고, 2로 도착하는 간선을 양방향 간선으로 바꿔주기만 하면 된다.

 위 단락에서 R2 = [4, 0, 6, 3]가 실제로 그림2에서 정점 2에서 정점 1,3,4로 가는 최단거리 배열과 동일하므로 원래의 인접리스트를 통해 'X에서 집까지'를 구할 수 있고, 역인접리스트를 통해 '집에서 X까지'를 구할 수 있으므로 두 배열을 더한 값이 총 거리가 된다. 따라서 최대값 갱신을 통해 정답을 구할 수 있다.

 

 # 코드

import heapq, sys

# dijstra : 정점 v에서 시작하여 2차원 행렬 arr을 기반으로 한 그래프에서 최단거리 배열 d를 리턴
def dijstra(v, arr):
    d = [INF] * vertex
    d[v] = 0
    min_q = []
    min_q.append((d[v], v))
    while len(min_q) != 0:
        distance = min_q[0][0]
        current = min_q[0][1]
        heapq.heappop(min_q)
        if d[current] < distance:
            continue
        for i in range(len(arr[current])):
            next = arr[current][i][0]
            nextdistance = arr[current][i][1] + distance
            if nextdistance < d[next]:
                d[next] = nextdistance
                heapq.heappush(min_q, (nextdistance, next))
    return d

INF = 100000000000

# 입력부 및 인접 리스트, 역인접 리스트 생성
vertex, edge, party = map(int, sys.stdin.readline().split())
adj = [[] for _ in range(vertex)]
n_adj = [[] for _ in range(vertex)]
for i in range(edge):
    start, end, time = map(int, sys.stdin.readline().split())
    adj[start - 1].append((end - 1, time))
    n_adj[end - 1].append((start - 1, time))

# party_to_home = 파티장에서 집까지의 최소 거리 배열
# home_to_party = 집에서 파티장가지의 최소 거리 배열
party_to_home = dijstra(party - 1, adj)
home_to_party = dijstra(party - 1, n_adj)

# ans : 총 거리를 저장하는 정답배열
ans = []
for i in range(vertex):
    ans.append(party_to_home[i] + home_to_party[i])
    
# 정답출력
print(max(ans))