doju   4년 전

출발 도시에서 도달할 수 있는 나가는 도로가 0개인 도시가 여러 개 있을 경우 틀린 답을 출력하는 코드들이 있습니다.

데이터를 확인하여 "출발 도시에서 어떻게 이동하더라도 항상 도착 도시에 도달할 수 있다"는 조건을 추가해 주시거나, 아래 데이터를 추가해 주시기 바랍니다.

doju   4년 전

일단 지금의 데이터는 위 조건을 만족하네요.

baekjoon   4년 전

조금만 더 자세히 설명해주세요. 이해가 잘 되지 않습니다.

doju   4년 전

위의 예시에는 나가는 도로가 0개인 도시로 가는 경로가 3개 있습니다. 1 - 2 - 3 (거리 3), 1 - 3 (거리 3), 1 - 4 (거리 2)
그런데 도착 도시가 4번 도시이므로 4번 도시에서 끝나는 세 번째 경로만 고려해야 하는데, 3번 도시에서 끝나는 경로까지 고려하여 3 3 을 답으로 출력하는 코드들이 있습니다.

"출발 도시는 들어오는 도로가 0개이고, 도착 도시는 나가는 도로가 0개이다"라는 조건만 있어서는 아예 연결된 그래프가 아니라서 출발 도시에서 도착 도시로 갈 수 없을 수도 있고, 위의 예시처럼 이상한 도시에 갇혀서 도착 도시로 갈 수 없게 될 수도 있습니다.

댓글을 작성하려면 로그인해야 합니다.