lynn529   3년 전

bfs를 사용해서 최단 거리를 구하고 dist에 저장해주었습니다.

queue에는 방문하고자 하는 node와 최단거리를 저장했습니다.

v1에서 모든 노드로의 최단거리를 구하고 v2에서 모든 노드로의 최단 거리를 구한 뒤 

(1 - v1 - v2 - n) 과 (1 - v2 - v1 - n) 의 거리를 비교해서 답을 구해줬습니다.(bfs 총 2번 실행)

틀렸다고 뜨는데 어디가 틀린걸까요...

아래는 해 본 테스트 케이스 입니다

4 5
1 2 10
1 3 11
2 3 20
2 4 30
3 4 100
2 3
답: 61
--------------------
3 3
1 3 20
1 2 15
2 3 6
1 3
답: 20

---------------------
4 5
1 2 3
1 3 1
1 4 1
2 3 3
3 4 4
2 3
답: 8
---------------------

7 7
1 2 3
3 2 5
1 3 1
6 5 3
7 5 8
5 4 2
6 4 3
2 6
답: -1
---------------------

2 0
1 2
답: -1

djm03178   3년 전

채점 환경에서는 예제도 제대로 출력되지 못합니다. 그 이유는 11번째 줄의 사용이 잘못되었기 때문입니다.

원하신 것은 dist가 가리키는 배열 전체를 -1로 초기화하는 것이지만, sizeof(dist)는 그 포인터가 가리키는 배열의 크기가 아니라 포인터의 크기를 나타내기 때문에 어떤 환경에서는 4, 채점 환경을 비롯한 어떤 환경들에서는 8이 됩니다. 4가 되는 환경에서는 dist가 가리키는 배열의 0번째 인덱스만 초기화되는데 이렇게 하면 의도와는 상관없이 우연히 답이 나오고, 8이 되는 환경에서는 아무것도 출력되지 않고 끝납니다. dist를 -1로 초기화하지 않고 그대로 두는 편이 오히려 나머지 라인들의 로직에 더 가까운 것 같습니다.

그리고 이와 같이 간선에 가중치가 있는 문제는 BFS로 풀 수 없고 다익스트라를 써야 합니다. 이 코드는 간선을 적게 사용하지만 거리는 더 먼 경로를 그 정점까지의 최단경로로 미리 확정짓고 있기 때문에 나중에 간선을 더 많이 사용하지만 거리는 짧은 경로를 발견하더라도 갱신하지 않고 넘어가게 됩니다.

lynn529   3년 전

다익스트라로 수정하니 해결되었습니다....

정말 감사합니다!!!

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