[BOJ] 1238번 - 파티

아는 형과 같이 알고리즘을 풀다가 이 문제에서 좋은 것을 배워 포스팅 해보려고 한다. 

배운 만큼 블로그도 한 번 홍보해보겠다. (좋은글 많아요~!)

degurii.tistory.com/

데구리 블로그

다시 본론으로 돌아가 보자.

단순히 문제만 봤을 때는 다익스트라 혹은 플로이드 와샬 알고리즘으로 풀 수 있을 것 같아 안 풀고 넘어가려고 했지만,

아는 형 말을 듣고 얼른 기억 해놨다가 오늘 풀게 되었다.

 

물론 실제로 다익스트라로 이 문제를 풀 수 있을 것 같지만, 점의 제한 개수가 많아지거나 한다면 시간이 좀 빠듯할 수 있다.

플로이드로 풀기엔  O(N^3) 이기 때문에 시간 초과가 날 것이다. 

 

www.acmicpc.net/problem/1238

1238번: 파티

문제를 봤을 때 풀어야할 것을 생각해보자.

 

1. 파티가 일어나는 장소에서 다른 장소로의 최단거리 값 계산 (다익스트라 활용)

 

2. 다른 정점들로부터 파티가 일어나는 장소까지의 최단거리 값 계산

 

1번은 한 번만 돌려도 되기 때문에 당연시 구현해야하는 것이고, 2번을 볼 때 문제가 될 수 있다.

2 번을 봤을 때 아 그냥 vertax만큼 다익스트라를 돌려보자 생각할 수도 있다. 하지만 그만큼 돌려버리면 시간도 많이 걸릴 뿐더러

굳이 필요없는 값 까지 구해버리기 때문에 최적화 시키지는 못한다.

글쓴이는 아는 형에게 재밌는 사실을 들었다. 1, 2번 결국 한 장소에서 최단 거리 값을 구하는 것인데 

 

예를들어 파티를 구하는 정점을 K라고 칭해보자.

 

그래프 1번을 봤을 때 각 점에서 K까지의 거리는 각각 4, 5 이다. 하지만 간선방향을 바꾼 뒤 K기준으로

최단거리 역시 4,5 로 똑 같이 구 할 수 있다.

 

아주 간단하게 생각만 해본다면 각 정점에서 다른 정점으로 부터 오는 거리를 측정했다고 보는 것이다. 

1번에서 각 정점을 기준으로 다른 정점에서 오는 거리들을 나타낸 그래프가 결국 2번 그래프가 되는 것이다.

 

위의 그림의 예가 좀 설명이 부족할 수있어, 점 하나를 추가해 보았다.

 

위와 똑같은 상황이다. 역시 간선을 뒤집어 봤을 때 2번그래프에서 K의 기준으로 다익스트라를 하게 되면

dist[] 배열에 각 정점으로부터 K점까지 최단거리가 나오게 된다.

 

모호하게 들릴 수 있지만, K정점을 기준으로 각 정점으로부터 올 수 있는 간선들을 다익스트라 알고리즘으로 돌렸을 때

K 에서 각 정점까지 갈 수 거리의 최단거리라 볼 수 있지만, 그래프를 뒤집었기 때문에 

갈 수 있다 -> 올 수 있는 으로 바뀌게 되는 것이다.

 

이것을 이용해 짠다면 시간복잡도를 더욱 줄 일 수 있게 된다.

 

from sys import stdin
from heapq import heappush, heappop

std = stdin.readline

N, M, x = map(int, std().split())

INF = 1000000001
# 순방향 간선
road = [[]for i in range(N)]

# 역방향 간선  //  다른 지점으로 부터 올 수 있는 거리를 구하기 위함
road_reverse = [[]for i in range(N)]

for i in range(M):
    a, b, d = map(int, std().split())
    road[a-1].append((b-1, d))
    road_reverse[b-1].append((a-1, d))

x = x-1
q = [(0, x)]


def dijkstra(k, func):
    dist = [INF for i in range(N)]
    dist[k] = 0

    while q:
        distance, vertax = heappop(q)
        if distance > dist[vertax]:
            continue
        for v in func[vertax]:
            ver, d = v
            if distance + d < dist[ver]:
                dist[ver] = distance + d
                heappush(q, (dist[ver], ver))

    return dist


go = dijkstra(x, road)
q.append((0, x))
back = dijkstra(x, road_reverse)
answer = 0

for i in range(N):
    if go[i] == INF or back[i] == INF or i == x:
        continue
    if answer < go[i]+back[i]:
        answer = go[i]+back[i]

print(answer)