어제 밤새 내내 고민하다가 오류를 찾지 못해서 도움을 구하고자 합니다. 어디서 코드 오타가 난건지, 아니면 알고리즘이 반례가 있는건지 ㅠㅠ

제가 구상한 알고리즘은 다음과 같습니다.

정점만 놔두고 일단 간선은 모두 지운 다음, 다음 규칙에 의해 필요한 간선을 하나씩 그어 나갑니다. 약간 플로이드+그리디 알고리즘인데요

1. 현재 입력받은 값 중 남아있는 값에서 최솟값을 택해 간선을 긋고, 플로이드를 돌린다.

2. 민호가 가진 값과 일치하게 되는 최솟값이 나왔다면 지운다. 남아있는 값들에 대해 1번을 반복한다.

- 만약 플로이드를 돌려 민호가 가진 값보다 작은 값이 나온다면 불가능 처리한다.


+) 영자님 문제 풀다가 어디서 틀린지 모르겠으면 틀린 test case를 확인할 수 있는 방법은 없나요?

우선 알고리즘적인 문제보다 구현적인 부분에서 문제가 있는 듯 합니다.

3
0 1 2
1 0 2
1 2 0

과 같은 인풋에서 1->3과 3->1의 거리가 다르므로 -1을 출력해야 하는데 그렇지 않고 있습니다.

구현을 adj[i][j]와 adj[j][i]둘 다를 고려하도록 바꾸시는게 좋을 듯 합니다.

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