플로이드-와샬 알고리즘을 공부하면서 "어차피 삼중 포문 처리에 첫번째, 두번째 포문 스코프에서 다른 처리는 하지 않으니 i j k 순서(관습적으로 쓰이는 순서대로 표현)대로 포문을 돌려도 되지 않을까" 생각했고, 실제로 그렇게 짜서 돌렸는데 오답이 났습니다. 그런데 k i j 순서로 포문을 돌리니 정답으로 처리되었습니다.
어차피 i j k로 루프를 돌리나 k i j로 루프를 돌리나 처리되는 값들은 똑같을텐데, 왜 i j k로 포문을 돌리면 오답이 날까요?
알고리즘을 공부할 때 이 알고리즘이 어떻게 해서 옳은 결과를 도출하는지 그 증명을 함께 이해하셔야 합니다.
이미 수많은 문서가 있으니 제가 한번 더 적기보다는 잘 정리된 문서를 읽어보시는 게 좋겠습니다. 한국어 위키 플로이드-워셜 문서의 알고리즘 문단을 참고하시면 원리를 이해하실 수 있습니다. 그 다음 해당 증명이 인덱스 순서를 바꿨을 때 적용되는지 고민해보면 아마 그렇지 않다는 걸 금방 아실 수 있을 겁니다.
belline0124 1년 전 1
안녕하세요, 플로이드-와샬 알고리즘 사용하다가 궁금한 점이 생겨서 작성합니다.
41439278번 소스코드(오답)와 41439499번 소스코드(정답)의 차이는 반복문 순서 차이밖에 없습니다. (19번째 라인~21번째 라인)
플로이드-와샬 알고리즘을 공부하면서 "어차피 삼중 포문 처리에 첫번째, 두번째 포문 스코프에서 다른 처리는 하지 않으니 i j k 순서(관습적으로 쓰이는 순서대로 표현)대로 포문을 돌려도 되지 않을까" 생각했고, 실제로 그렇게 짜서 돌렸는데 오답이 났습니다. 그런데 k i j 순서로 포문을 돌리니 정답으로 처리되었습니다.
어차피 i j k로 루프를 돌리나 k i j로 루프를 돌리나 처리되는 값들은 똑같을텐데, 왜 i j k로 포문을 돌리면 오답이 날까요?