1774번 - 우주신과의 교감
이 문제 게시글을 보다가 이문제를 위한 프림, 쿠르스칼의 알고리즘이 있다는것을 알게 되었습니다. 단계별로 풀기를 진행하면서 다익스트라 풀면서 이문제에 접근하게 되어 다익스트라를 살짝 변형했습니다.(게시글에 있는 예제 두개 모두 합격했습니다)
뼈대 코드 :
문제 : https://www.acmicpc.net/problem/4386
코드 : https://www.acmicpc.net/source/23391175
알고리즘 설명
한점을 임의로 지정하고 그점에 연결된 가장 짧은 간선을 선택합니다.
그점을 사용하여 다른 점으로 이동합니다. 두점을 잇는 간선이 아닌 두점과 연결된 가장 짧은 간선을 선택하여 점 3개를 잇습니다.
그런식으로 연결된 점들을 하나씩 늘려갑니다.
이 알고리즘이 어디가 문제인지 모르겠습니다. 지적 달게 받겠습니다.
혹시나 해서 float에서 double로 바꾸니까 해결되네요ㅋㅋ....
코드는 남겨놓겠습니다.
댓글을 작성하려면 로그인해야 합니다.
minjun623 3년 전
이 문제 게시글을 보다가 이문제를 위한 프림, 쿠르스칼의 알고리즘이 있다는것을 알게 되었습니다. 단계별로 풀기를 진행하면서 다익스트라 풀면서 이문제에 접근하게 되어 다익스트라를 살짝 변형했습니다.(게시글에 있는 예제 두개 모두 합격했습니다)
뼈대 코드 :
문제 : https://www.acmicpc.net/problem/4386
코드 : https://www.acmicpc.net/source/23391175
알고리즘 설명
한점을 임의로 지정하고 그점에 연결된 가장 짧은 간선을 선택합니다.
그점을 사용하여 다른 점으로 이동합니다. 두점을 잇는 간선이 아닌 두점과 연결된 가장 짧은 간선을 선택하여 점 3개를 잇습니다.
그런식으로 연결된 점들을 하나씩 늘려갑니다.
이 알고리즘이 어디가 문제인지 모르겠습니다. 지적 달게 받겠습니다.