대체 경로 - 구름LEVEL

문제 정보

대체 경로

보통

유형

프로그래밍

배점

100점

참여자

407

정답률

97%

문제

플레이어는 번부터 번까지의 번호가 붙은 개의 도시와 개의 도로가 있는 나라에 살고 있다. 각 도로는 서로 다른 두 도시를 양방향으로 연결하고 있고, 주어진 도로만을 이용해 임의의 두 도시 사이를 이동하는 것이 가능하다.

플레이어는 차를 타고 번 도시에서 번 도시로 이동하려고 한다. 플레이어가 두 도시 사이를 이동할 때는 항상 가장 작은 수의 도시를 거치는 경로를 따라 이동한다. 예를 들어 아래 그림과 같이 도시와 도로가 주어지고, 플레이어가 1번 도시에서 4번 도시로 이동하려고 할 때는 항상 1 → 3 → 4의 경로를 따라 이동한다. 이 경우에는 출발 도시와 도착 도시를 포함해 총 세 개의 도시를 거쳐 이동할 수 있다. 1 → 5 → 2 → 4의 경로로 이동하는 것은 출발 도시와 도착 도시를 포함해 네 개의 도시를 거치는 경로이므로, 플레이어는 해당 경로로는 이동하지 않을 것이다.

항상 가장 작은 수의 도시를 거치는 경로가 유일하지 않을 수 있다. 아래 그림과 같이 도시와 도로가 주어지고, 3번 도시에서 1번 도시로 이동하고자 할 때 가장 작은 수의 도시를 거치는 경로는 3 → 2 → 1과 3 → 4 → 1의 두 개가 있다. 이런 경우에 플레이어는 두 경로 중 아무 경로나 택해서 이동한다.

플레이어가 사는 나라에서는 자주 공사를 한다. 일 뒤에는 번 도시에서 하루 동안 공사를 할 예정이다. 어떤 도시에서 공사를 하고 있으면, 그 도시에 연결된 모든 도로를 일시적으로 사용할 수 없다.

어떤 도시에서 공사를 하느냐에 따라 플레이어가 이동해야 하는 경로가 달라질 수 있다. 앞으로 일 동안 매일 플레이어는 번 도시에서 번 도시로 이동한다고 할 때, 각 날마다 플레이어가 이동하는 경로에 포함되는 도시의 수를 구해서 출력해보자. 단, 출발 도시와 도착 도시에서 공사를 하거나, 두 도시 사이를 이동할 수 없는 경우에는 -1 을 대신 출력한다.

예제 설명

첫 번째 예제는 지문의 첫 번째 그림에 해당하는 예시이다.
1번 도시와 4번 도시가 공사 중일 때는 항상 두 도시 사이를 이동할 수 없다.
2번 도시와 5번 도시가 공사 중일 때는 1 → 3 → 4의 경로를 따라 이동할 수 있다. 경로에 포함된 도시는 세 개이다.
3번 도시가 공사 중일 때는 1 → 3 → 4의 경로를 따라 이동할 수 없다. 따라서 1 → 5 → 2 → 4의 경로로 이동해야 하고, 이때 경로에 포함된 도시는 네 개이다.