BOJ 문제풀이/최단경로 (Shortest Path) 썸네일형 리스트형 백준 4485 : 녹색 옷 입은 애가 젤다지? https://www.acmicpc.net/problem/4485 전형적인 다익스트라 알고리즘 문제이다.한 지점을 기준으로 특정 지점까지 최단경로를 구하고 양수인 가중치가 주어질 때 다익스트라를 활용할 수 있다. 각 점을 기준으로 상,하,좌,우가 연결되있고 priority_queue에 최단경로를 갱신하면서 넣어주면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53#include #include #define MAX 126 #define INF 1000000000 using names.. 더보기 백준 2211 : 네트워크 복구 https://www.acmicpc.net/problem/2211 처음에 최소스패닝트리(MST) 문제인지 헷갈려서 삽질을 했다. 그러나 위의 (2)번 조건에 의해 결국 다익스트라로 해결해야 한다.모든 컴퓨터들이 1번 슈퍼컴퓨터와의 최소경로를 만족해야한다. 따라서 1번을 기준으로 다익스트라를 해주고 각 컴퓨터들에 저장된 이전 정점 정보를 가져와 연결하면 된다. Com 구조체에 현재 거리 뿐만 아니라 이전 정점의 정보까지 저장해야 한다.struct com{int idx, dist = INF, post = 0;}; 다익스트라를 돌면서 최소 거리를 갱신해줄 때 post값도 갱신해주면 된다.for(현재 정점과 연결된 모든정점 탐색){if(다음 정점의 거리 > 현재정점까지 거리 + 간선의 가중치){//최소거리 갱신.. 더보기 백준 1504 : 특정한 최단 경로 https://www.acmicpc.net/problem/1504 다익스트라 알고리즘인데 조건이 추가되었다. 바로 주어진 두 정점을 반드시 거쳐가야하는 것이다.시작점을 1, 두 정점을 n1, n2, 끝점을 n 이라고 한다면 1-->n1-->n2-->n또는1-->n2-->n1-->n 루트의 두가지 방법이 있다. 각각 --> 과정에서는 다익스트라로 최소의 경로로 진행한다.지나온 길을 다시 거쳐갈 수 있기때문에 각각 다익스트라로 최소비용을 구한다음 합쳐주는 것이가장 짧은 루트이다. 이 때 총 세 번의 다익스트라로 모든 루트를 구할 수 있다. 1. 1-->n1, 1-->n2 2. n1-->n23. n-->n1, n-->n2 를 구한다음 2개의 경로중에 더 작은 것을 선택해주면 됨. 1 2 3 4 5 6 7 8 .. 더보기 백준 1916 : 최소비용 구하기 https://www.acmicpc.net/problem/1916 역시 최단경로 기본문제이다.한 점에서 다른 점으로 도달하는데 가중치가 있고 최소비용을 구해야 한다면 Dijkstra를 고려하자. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51#include #include #include #define MAX 1001 #define INF 1000000000 using namespace std; int n, m, init, target; struct City{ int idx, dist = INF; .. 더보기 백준 1753 : 최단경로 https://www.acmicpc.net/problem/1753 최단경로 기본문제. 한 정점을 기준으로 다른 정점까지 최단 경로를 구할때 만약 간선의 가중치가 없으면 BFS로 탐색하면 된다.만약 간선의 가중치가 존재하면 기본적으로 다익스트라(Dijkstra) 알고리즘을 사용할 수 있다. 다익스트라 알고리즘은 BFS와 형태가 유사한데while문에 queue 대신 priority_queue를 넣고 너비우선탐색처럼 정점을 순회하며각 정점의 최단경로를 갱신하는 방법이다. (priority_queue를 쓰는 것은 다익스트라 알고리즘을 ElogV 로 최적화 한 것이다.) 각 정점에 연결된 간선의 정보를 넣고 다음 정점을 탐색할때 만약 (다음 정점의 Distance > 현재정점의 Distance + 간선의 가중치).. 더보기 이전 1 2 다음
