백준에는 5214번 환승 문제와, 2021번 최소 환승 알고리즘을 구하는 문제가 있습니다. 이 두 문제 중에서 후자를 풀어보겠습니다.

 


 역의 갯수 n과 노선 갯수 L은 둘 다 10만 이하라는 조건은 꽤 무시무시하게 다가옵니다. 각 노선 길이의 합은 100만을 넘지 않는다는 조건을 잘 이용해 봐야 할 듯 싶네요. 여기서 핵심은 '환승을 한다'는 것을 어떻게 그래프로 표현을 할 것인지입니다. 학교 과제에서도 왕왕 나오는 편이니, 이야기를 해 보도록 하겠습니다.

 

 노선 1과 노선 2가 만나는 환승 역 j를 생각해 봅시다.

 

 

 그래프는 요렇게 그려질 수 있습니다. 여기서 핵심은, j번 역을 통해서 노란색에서 파란색으로, 혹은 파란색에서 노란색 노선으로 건너갈 수 있다는 것입니다.

 

 

 3개 노선이 만나는 j역이면 어떨까요? 마찬가지로 그리면 됩니다. j역을 통해 주황색에서, 노랑, 파랑으로, 노란색에서 주황, 파랑으로, 파랑색에서 주황, 노랑으로 갈 수 있습니다. 이것을 그래프로 표현하면 위와 같습니다. 즉, 우리는 k번 역이 노선 a(1), ... , a(u)와 만났을 때, k번 역에서, 노선 a(i)에서 노선 a(j)로 갈아타는 비용을 1로 설정하는 전략을 취했습니다. 당연하게도, i와 j는 [1, u] 범위에 속하는 정수였을 겁니다. 문제는 이런 경우입니다.

 

 

 이 경우에는 그래프가 어떻게 그려질까요? 노선이 1, 2, 3, 4, 5가 있고, 모두 1번 역을 지나는 경우에는 아래와 같이 그려질 겁니다.

 

 

 10만개라면, 10만C2개의 간선이 그려질 겁니다. 시간 초과가 나는 건 당연한 이야기일 겁니다.

 

 


 연결하는 간선을 줄이는 전략이 필요합니다. 해당 아이디어만 조금 수정해 봅시다. 우리는 아래와 같은 전략을 도입할 수 있습니다.

 

 

 예를 들어보겠습니다. 2개 노선이 만나는 환승역부터 출발해 봅시다.

 

 

 주황색 노선에 있는 j에서 노란색 노선에 있는 j로 갈 때, hub 지점을 거쳐서 가는 것을 표현한 그래프입니다. 3개 노선인 경우에는 어떻게 하면 될까요? 1번에서 2, 3번으로 넘어가는데도, 2번에서 1, 3번으로 가는 데도, 3번에서 1, 2번으로 가는 데도 hub를 거친다.

 

 

 이렇게 그리면 직관적일까요? 임의의 노선에서, 다른 노선으로 넘어갈 때, 무조건 허브를 거쳐서 넘어가게 됩니다. 그러므로, 이렇게만 해 두고, hub로부터 지하철 노선까지 가는 거리를 1로 두면 됩니다. 4개일 때도 마찬가지로 하면 될까요?

 

 

 그래도 됨을 알 수 있습니다. 즉, 우리는 n개의 노선이 환승하는 역을 표현하기 위해서, nC2개의 간선이 필요했던 것을, n개의 간선만 넣으면 될 수 있게 개선하였습니다.

 


 이제 남은 것은, 역 번호와 허브들의 번호를 어떻게 할 것이냐입니다. 노선이나 역의 갯수는 미리 알 수 있습니다. 그러므로, 허브의 번호를 1부터 10만까지 할당해 놓는 편이 간단합니다.

 

 

  다음에 입력받은 노선 역 순서대로 10만 1부터 할당하는 편이 간단합니다. 예를 들어, 1 3으로 이어지는 노선과, 2 3으로 이어지는 노선 둘을 입력받은 경우에 그래프는 위와 같이 그릴 수 있습니다. 실선의 경우에, cost를 1로 설정하면 됩니다. hub를 거쳐서 환승이 되기 때문에, 실제로 답을 출력할 때에는 답에 0.5를 곱하면 됩니다. 혹은, 허브를 정점 분할하는 방법도 생각해 볼 만한 방법입니다. 그런데, 시간 제한이 걸립니다.

 

 

 n이 4개, 1 2, 2 3, 2 3 4를 잇는 노선 3개가 들어왔을 때 그래프 구조는 위와 같습니다. 좋은 방법이고, 실제로 이렇게 모델링을 했을 때 아슬아슬하게 통과합니다. 그런데, 많은 코드들이 1초의 제한시간이 너무 널널할 정도로 빠르게 통과해 버립니다.

 

 


 더 효율적인 방법이 없을까요? 핵심은, 같은 노선 내에서 이동하는 경우에는 무조건 비용이 0이라는 것입니다. 그러면, 우리에게 중요한 정보는 hub와 노선 간의 연결 관계입니다. 그러므로, 해당 노선이 몇 번 허브를 연결하는지에 대한 정보만 들고 있으면 됩니다. 허브와 노선에 있는 역을 연결하는 간선을 지나갈 때만 비용이 들기 때문입니다.

 

 

 다시 이 그래프에서 출발해 봅시다. 노선과 환승 허브. 이 둘만 생각하면 생각보다 쉽게 압축을 시킬 수 있습니다. 1번 노선은 1, 3번이 환승역입니다. 그러므로, 1번 노선이 1, 3번 역의 허브와 연결하는 형태가 됩니다.

 

 

 요런 형태가 될 수 있습니다. 다음에, 2번에 대해서도 똑같이 해 봅시다. 2번 노선은, 2번과 3번 hub와 연결되어 잇습니다.

 

 

 따라서, 노선 2도 이렇게 압축시킬 수 있습니다. 다음에 노선 3은 2, 3, 4로 이루어져 있는데요. 이것은 2번, 3번, 4번 허브와 이어집니다. 요것도 compress를 시키면 아래와 같습니다.

 

 

 노드는 최대 20만개, 간선은  최대 100만개를 쓰게 됩니다. 노드가 매우 많이 줄어든 것이 포인트입니다.

 

 

 그래프는 아래와 같이 구축하면 됩니다. aa[a]는 a번 허브에 어떤 노선이 연결되어 있는지를 나타냅니다. 시작점 s로부터 도착점 e까지 최소 환승 횟수를 구한다면, s번 허브가 몇 번 노선과 연결되어 있는지 알아내서, 그 노선들부터 큐에다 넣고 탐색하면 되겠네요.