5214. 환승

종강했다. 이제 하고 싶은 공부 할 수 있다.

5214번: 환승

---

``하이퍼튜브``라는 교통수단이 주어진다. ``하이퍼튜브``는 $K$개의 역을 서로 연결한다고 주어져 있는데, 이것은 같은 튜브에 속하는 모든 역간 거리가 1이라는 의미이다. 물리적인 길이라고 생각하면 틀릴 수 있으니 주의.

 

아무튼 문제 자체는 어렵지 않다. 골드1임에도 불구하고 간단한 BFS로 풀 수 있다. 같은 튜브에 속하는 모든 정점을 서로 연결하고, 1번에서 출발하는 BFS를 수행하면 된다.

 

물론 이렇게 해도 문제를 풀 수는 있지만, 시간이 1036ms나 걸리는 걸 보니 문제의 의도가 따로 있는 듯 하다. 시간을 줄여 보자.

---

내 코드에서 가장 오래 걸리는 부분은 BFS에서 어떤 노드와 연결된 다른 노드를 찾는 부분이다. 자세히 살펴보면 내 코드는 튜브 하나당 $\left(\begin{array}{c}k\\ 2\end{array}\right)$개의 간선을 만든다. 따라서 이론적으로 최대 $1000\left(\begin{array}{c}1000\\ 2\end{array}\right)=499,500,000$개의 간선이 존재할 수 있다. 그렇다, 이 문제를 해결하려면 간선을 줄여야 한다.

 

내 코드에서는 ``예제 입력 1``에서 1번 역과 연결된 모든 노드를 한번에 알 수 없다. 왜냐하면 1번 역이 두 개의 튜브에 속하기 때문이다. 따라서 1번 역이 포함된 모든 튜브에 대해, 각 튜브가 포함하는 모든 역을 살펴봐야 한다.

 

이 부분을 다음과 같이 개선할 수 있다. 각 튜브를 의미하는 $i'$번 역을 정의하자. 그러면 $i'$번 튜브에 속하는 모든 $i$번 역에 대해 $i$번 역과 $i'$번 역이 서로 연결된다. 이렇게 하면 간선 $2K$개만을 사용하여 튜브를 표현할 수 있다. 저 위의 이차식보다 훨씬 낫지 않은가?

 

이제 기존의 방법대로 거리를 구하면 된다. 다만 원래 코드에서는 같은 튜브에 속하는 두 정점이 직접 연결되어 있었는데, 지금은 중간에 ``튜브 역``이 끼어 있으므로 정답을 그대로 출력하면 안 된다. BFS로 구한 거리를 $d$라 하면, 역 두개마다 ``튜브 역``이 끼어 있으므로 실제로 구하는 정답은 $\frac{d}{2}+1$이다.

---

시간이 크게 향상되었다.

노드 사이에 더미 노드를 끼워 BFS하는 패턴을 기억하자.