파티 참석하기 2 - PARTY2

문제 링크(koitp.org/problem/PARTY2/)

STL 없이 코드를 작성해보았다.
우선, 이 문제에서 구하고자 하는 것은 max(dist(X→a)+dist(a→X))이다.
dist(X→a)는 X번 학생의 기숙사 방에서 a번 학생의 기숙사 방에 이르는 최단거리이다.
따라서 이 문제는 주어진 그래프에 대해 dist(X→a)와 dist(a→X)를 계산하면 풀 수 있다.

dist(X→a)는 주어진 그래프에서 점 X를 시작점으로 다른 점들에 이르는 최단 거리를 구하면 된다.
dist(a→X)는 주어진 그래프의 간선 방향을 뒤집은 다음(간선의 시작점과 끝점을 바꿈), 위와 마찬가지로 계산하면 된다.
정리하면, 원래 주어진 그래프(G1)에 대해 점 X에서 단일 출발점 최단경로 알고리즘을 수행하고, 주어진 그래프의 방향을 뒤집은 그래프(G2)에 대해 점 X에서 단일 출발점 최단경로 알고리즘을 수행하면 되겠다.

단일 출발점 최단경로 알고리즘으로 가장 일반적인 Dijkstra의 알고리즘이 있다.
여기선 SPFA(Shortest Path Faster Algorithm)를 소개하려 한다.
평균 시간 복잡도는 Dijkstra보다 빠르며 방법이 매우 단순하다.
SPFA는 일반적인 BFS(너비우선탐색) 구조에서 inQueue라는 개념이 더해진다.
inQueue(x)는 지금 추가하려는 정점이 x인데 이미 큐에 정점 x가 들어있는지에 대한 정보이다.
큐에 이미 x가 들어있음에도 불구하고, x에 이르는 최단 거리를 갱신할 때마다 큐에 x를 반복적으로 삽입하는 것은 의미가 없으므로(왜냐하면 어차피 큐에서 x를 꺼내서 다른 경로를 알아볼 때에는 이전까지 갱신된 최단 거리 값을 사용할 것이기 때문에), 이 아이디어를 이용한 것이다.
주의할 점으로, SPFA에 사용하는 큐의 크기는 상수*정점의 최대 갯수인데, 상수는 보통 50~100 정도로 설정하면 된다. 만약 상수를 작게 잡아서 만점이 나오지 않는다면, 메모리 제한이 허락하는 내에서 늘려보면 된다.
100점 받은 코드는 아래와 같다.

위의 코드를 보면, 간선의 정보를 (s, e, t, prv)로 표현하였다.
s는 간선의 시작점, e는 간선의 끝점, t는 간선의 가중치, prv는 시작점이 s이면서 이전에 등장한 간선의 index이다.
그리고 to(x)라는 것이 등장하는데, to(x)의 정의는 정점x에서 나가는 간선 중 가장 index가 큰 간선의 index(가장 나중에 입력받은 간선의 index)이다.
그림으로 표현하면 다음과 같다.

따라서 어떤 to(x)에 해당하는 index의 간선부터 보면서, prv를 따라가다가 index가 0이 되면, 시작점이 x인 간선들을 모두 훑어본 것이다.

힙을 이용한 다익스트라로 100점을 받은 코드는 아래와 같다.