Dijkstra6 [C/C++] 백준 #2665 미로만들기(다익스트라) 이번 문제는 얼듯 보면 미로를 백트래킹(또는 깊이우선탐색) 등으로 풀어나갈 것 같지만, 벽을 가는 곳을 간선 웨이트를 1로, 벽이 없는 곳을 간선 웨이트 0으로 생각하고 다익스트라 알고리즘을 적용하면 풀기 편합니다. https://www.acmicpc.net/problem/2665 제가 작성한 소스의 설명입니다. 일반적인 다익스트라 알고리즘을 이용했는데, 우선순위큐에 저장될 값들을 비트연산을 통해서 정수형(int)로 만들어서 했습니다. 1. **입력 받기**: 사용자로부터 미로의 크기 n과 미로의 지도를 입력받습니다.2. **우선순위 큐 사용**: 미로의 각 방을 탐색하기 위해 우선순위 큐를 사용합니다. 이 큐는 현재 경로에서 흰 방으로 바꿔야 할 검은 방의 수를 우선순위로 사용합니다.3... 2024. 6. 1. [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. [C/C++] 프로젝트 오일러 #82 path sum : three ways(다익스트라) 이번 문제는 앞에 #81 문제와 동일하게 경로의 합을 구하는데 있어서 최소의 경로값을 잦는 것입니다.앞의 문제가 two ways였던 것에 비해서 이번 것은 three ways입니다. 프로젝트 오일러 문제들 초창기가 제가 알고리즘 문제들 풀기 시작한 초기였던 점을 생각했을 때, 지금 보면 유치하기 짝이 없네요.일단 힙구조를 사용하지도 않고 짰고, 삽입정렬을 이용해서 짰네요. 뭐 삽입정렬을 한다고 한다면, O(N2) 알고리즘이었다는 것이죠. 이것 작성할 때만 해도 STL 사용도 안 했을 때이니까요. 우선순위 큐를 사용하면 해결되었을텐데요. 행렬이 크기 않았기 때문에 풀 수 있던 것이죠. 동적 계획법으로 풀 수도 있습니다. 하지만 사이클이 있기때문에 반복을 많이 해야 안정된 값이 나오게 됩니다.. 2022. 10. 10. #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
