반응형 Dijkstra4 [C/C++] 프로젝트 오일러 #83 Path sum: four ways(다익스트라) #83 문제는 난이도 25%로 설정되어 있습니다. 동적 계획법 등으로는 구현하기 어렵고, 다익스트라 알고리즘을 사용해야 합니다. 다익스트라 알고리즘 자체는 너비 우선 탐색, 프림 알고리즘과 비슷한 구현 방법으로 큐 자료구조와 우선순위 큐 자료구조의 이해가 필요합니다. https://projecteuler.net/problem=83 다익스트라 알고리즘 구현은 그래프에서 경로 찾기에서 자주 나옵니다. https://sdev.tistory.com/119 다익스트라 알고리즘 다익스트라 알고리즘은 시작점에서 다른 모든 경로로 가는 최단 거리에 대한 그래프(트리)를 만들어줍니다. 다익스트라 알고리즘을 사용하려면, 힙을 이용해서 최소의 엔티티를 찾는 것이 필요 sdev.tistory.com https://sdev.t.. 2023. 5. 6. #1504 특정한 최단 경로 특정한 최단 경로는 중간에 두군데의 지점을 반드시 통과하는 경로중 최단 경로를 찾아라하는 문제입니다. 중간에 두군데의 지점을 반드시 통과하기 위해서는 [시작]-[지점1]-[지점2]-[끝]을 가는 경로와 [시작]-[지점2]-[지점1]-[끝]을 가는 경로중 거리가 짧은 것을 선택하시면 됩니다. 기본적인 알고리즘은 다익스트라(Dijkstra)의 변형입니다. 다익스트라 변형은 도착지점이 큐에서 나오면, 더이상 계산하지 않도록 하는 것입니다. 무방향 그래프이므로 [지점1]-[지점2]와 [지점2]-[지점1]은 같은 값입니다. 제가 구현한 소스입니다. 소스는 참조용으로만 봐주세요. //--------------------------------------------------------------------------.. 2022. 8. 22. #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 다음 728x90
