sj155   1년 전

모르겠어서 다른 분들의 코드 보고 3중 for문이 많다는 것을 알게 되었습니다.

2중 for문으로 하면 문제가 풀리지 않는 이유를 알고 싶습니다.(아니면 제가 짠 코드가 잘못된 건가요)

유니온 파인드를 사용한 이유는 서로만 연결되어 있는 도시끼리 음수 사이클을 가지는 경우 출발점에서 도달하지 못하기 때문입니다.

djm03178   1년 전

3중 for문이 단순한 아이디어에서 나오는 것이 아니라 벨만 포드라는 알고리즘을 사용한 것입니다.

sj155   1년 전

제 생각에 대한 설명이 부족했던것 같습니다.

이 문제는 벨만 포드 알고리즘으로 푸는 것을 알고 있습니다.

저는 2중 for문으로도 풀 수 있다고 생각합니다.

그런데 2중 for문으로는 다른 분들의 글을 보고 코드를 복사해서 돌려봐도 틀렸다고 나와서

3중 for문으로 푸는 방법을 알고 싶습니다.

djm03178   1년 전

3중 for문이 어떤 코드를 보셨는지는 모르겠는데 지금 코드랑 다를 게 없습니다. 아마도 그 코드들은 간선 정보를 크기 m의 배열에 모으는 대신 시작점에 따라 나누어서 저장했기 때문에 [n번의 루프 동안 {모든 시작점에 대해 (각 시작점에서 나가는 간선들을 확인)}] 하는 방식으로 구현했을 것입니다.

이 코드는 그냥 다음과 같은 입력이 반례입니다.

djm03178   1년 전

그리고 inf값도 너무 작아서 1번과의 연결 여부도 올바르게 판정을 할 수 없습니다.

sj155   1년 전

답변 감사합니다. 

좀 더 생각해보겠습니다.

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