반응형 다익스트라8 #1445 일요일 아침의 데이트 일요일 아침의 데이트는 다익스트라 알고리즘을 이용하는 문제로 Gold II 문제로 잡혀 있습니다. 아침에 산책을 하면서 야외에서 커피를 같이 마시면 즐겁겠죠? 다익스트라 알고리즘을 알고 있는 분들은 어렵지 않게 풀 수 있습니다. 일단 맵을 읽으면, 이 맵을 적절하게 변환을 해주었습니다. 예제와 같이 입력이 주어진다면, 6 6 ...... g..F.. ...... ..g... ...... ...S.g 저는 이 입력을 다음과 같은 형태로 변환을 했습니다. 쓰레기가 있는 주변을 1로 만들고, 쓰레기는 10,000의 값으로 채웠습니다. S, F는 세지 않는다고 했으니, 추후에 그 부분은 다시 0의 값으로 만들고요. 1 0 0 0 0 0 10K 1 0 0 0 0 1 0 1 0 0 0 0 1 10K 1 0 0 0 .. 2022. 8. 9. 다익스트라 알고리즘 다익스트라 알고리즘은 시작점에서 다른 모든 경로로 가는 최단 거리에 대한 그래프(트리)를 만들어줍니다. 다익스트라 알고리즘을 사용하려면, 힙을 이용해서 최소의 엔티티를 찾는 것이 필요하겠지만, 일단은 간단하게 구성해보았습니다. (참조 : http://sdev.tistory.com/72 , http://sdev.tistory.com/71) 이 소스는 애시당초 프림 알고리즘 소스를 만들었던 것을 고친지라, 코멘트가 프림에 맞추어져 있습니다. // Dijkstra.cpp : Defines the entry point for the console application. // #include "stdafx.h" #defineNIL(0) ///인접리스트를 위한 구조체 선언 struct vlist { int vert.. 2014. 10. 18. 이전 1 2 다음 728x90
