qwqw8019   2년 전

16%에서 수없이 실패한 결과를 공유드리면 도움이 되지않을까 싶어 남깁니다.


1. INF + INF = INF 이므로 초기값을 INF가 아닌 1_000_000_000으로 초기화 해야합니다.

반례) S->G = INF, H-> ti= INF 이 경우에, ti로 이동할 수 없음에도 불구하고 |S->ti| == |S->G| + |G->H| + |H -> ti|의 결과값이 참이므로 틀리게 됩니다.

2. 정렬 순서를 주의합시다.(이것 때문에 삽질을 좀 했습니다.)

문제의 "목적지들을 공백으로 분리시킨 오름차순의 정수들로 출력한다." 와 같이, 정수를 기준으로 오름차순 정렬해야 하는데, 이를 무시하고 answer 배열에 String으로 넣은 후 print(" ".join(answer))를 출력해서 틀렸습니다.

반례) 정답에 속하는 목적지들이 [4, 1, 3, 11]인 경우, "1 3 4 11"이 정답이지만, String으로 정렬하게 되면  "1 11 3 4"가 되어 틀리게 됩니다. (사전식으로 정렬하기 때문)

기초적인 실수이지만 주의해야겠습니다.

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