ekdrn1   1년 전

4 4
1 2
2 3
3 4
1 4
1 4

정답: 2 ( 1 - 4 - 1 )

10 12
1 2
2 4
4 5
5 7
1 3
3 4
4 6
6 7
3 10
10 9
9 8
8 6
1 7

정답: 10

88%틀 해결에 도움이 될 수 있습니다.

chika   1년 전

안녕하세요 올려주신 반례 잘 봤습니다!
혹시 위쪽 input에 대해서 제가 보기엔 정답이 2인거 같은데, 체크 한번 해주실 수 있으실까요?

ekdrn1   1년 전

@chika

다시 확인해보았습니다만, 4가 맞는 것 같습니다!

preview

위 형태의 그래프이며, 1 - 4 - 3 - 2 - 1 순으로 이동해야 합니다!

chika   1년 전

답변 감사합니다. 근데 ‘최단경로’ 중에서 사전순으로 제일 빠른걸 고르는것이기 때문에 1 -> 4 -> 1 이 되지않을까요?

ekdrn1   1년 전

@chika

문제 조건을 다시 읽어보니까 맞는 말씀 같네요...?

한번 지나갔던 간선으로 다시 이동할 수 없는 것이 아니라

방문한 정점을 다시 방문하지 않는 것이니까요. (S, E 정점은 예외)

88%에서 막혔을때 해결하다가 반례 생각하면서 그렸던 건데, 틀린 것 같네요. 수정했습니다.

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