belline0124   1년 전

안녕하세요, 플로이드-와샬 알고리즘 사용하다가 궁금한 점이 생겨서 작성합니다.

41439278번 소스코드(오답)와 41439499번 소스코드(정답)의 차이는 반복문 순서 차이밖에 없습니다. (19번째 라인~21번째 라인)


플로이드-와샬 알고리즘을 공부하면서 "어차피 삼중 포문 처리에 첫번째, 두번째 포문 스코프에서 다른 처리는 하지 않으니 i j k 순서(관습적으로 쓰이는 순서대로 표현)대로 포문을 돌려도 되지 않을까" 생각했고, 실제로 그렇게 짜서 돌렸는데 오답이 났습니다. 그런데 k i j 순서로 포문을 돌리니 정답으로 처리되었습니다.

어차피 i j k로 루프를 돌리나 k i j로 루프를 돌리나 처리되는 값들은 똑같을텐데, 왜 i j k로 포문을 돌리면 오답이 날까요?

tori1753   1년 전

i j k 돌리는 순서에 따라 처리되는 결과가 달라집니다

belline0124   1년 전

구체적으로 어떠한 매커니즘때문에 결과가 달라지는건가요?

wider93   1년 전

안녕하세요. 

알고리즘을 공부할 때 이 알고리즘이 어떻게 해서 옳은 결과를 도출하는지 그 증명을 함께 이해하셔야 합니다.

이미 수많은 문서가 있으니 제가 한번 더 적기보다는 잘 정리된 문서를 읽어보시는 게 좋겠습니다. 한국어 위키 플로이드-워셜 문서의 알고리즘 문단을 참고하시면 원리를 이해하실 수 있습니다. 그 다음 해당 증명이 인덱스 순서를 바꿨을 때 적용되는지 고민해보면 아마 그렇지 않다는 걸 금방 아실 수 있을 겁니다.

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