백준 9370 : 미확인 도착지 https://www.acmicpc.net/problem/9370 기본적으로 한 지점에서 다른 지점으로 가는 최단경로가 필요한데 어떤 두 정점을 방문해야 하거나 한 간선을 들려야 한다면다익스트라 3번으로 최단경로를 구할 수 있다. start >> n1 -- n2 >> end 는 ① (start->n1) + (n1->n2) + (n2->end) 최단경로와 ②(start->n2) + (n2->n1) + (n1->end) 최단경로를 구할 수 있다. s를 기준으로 다익스트라 할 경우 s->end 까지 최소비용을 알 수 있다.그 값이 ① 또는 ② 둘중 하나와 같다면 end 후보지를 만족한다고 볼 수 있다. ※ 그런데, 더 획기적인 방법이 있다!! (시간이 엄청 짧은 사람의 풀이를 보다가 발견하였다.) 만약 가중치.. 더보기 백준 10282 : 해킹 https://www.acmicpc.net/problem/10282 어떤 컴퓨터x 가 동시에 a,b,c 3대의 컴퓨터를 의존한다고 했을 때 그 컴퓨터x 는 a 또는 b, c 에 의해 감염될 수 있다. 근데 이때 a,b,c 중 가장 감염이 빠른 컴퓨터 기준 걸린 시간 + s 만큼 컴퓨터x 가 감염이 되므로 결국 최단경로를 찾는다익스트라 알고리즘이다. 최소 경로를 갱신할 때 만약 이전 dist값이 INF이면 처음 감염된 컴퓨터이므로 count값을 ++ 시켜주는 것으로 감염된컴퓨터의 총 개수를 구할 수 있고 INF가 아닌 컴퓨터들의 dist중 max값이 가장 마지막 컴퓨터가 감염완료된 시점으로볼 수 있다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 2.. 더보기 백준 10473 : 인간 대포 https://www.acmicpc.net/problem/10473 한 정해진 출발지점에서 특정 도착지점으로 가는 최단 경로이자 각 노드마다 가중치(시간)가 다르므로 다익스트라로구현할 수 있다. 단 간선이 미리 주어져있지는 않아서 n^2 연산을 통해 모든 정점들을 다 연결하고조건에 따라 1. 대포를 타고 이동할 것인지(거리가 30m 이상이면 대포를 타는 것이 낫다.)2. 걸어서 이동할 것인지 계산해 가중치를 설정해주었다. 이 때 대포를 타든 걸어서 가든 정점과 정점을 사이를 이동할때는일직선으로 이동한다고 가정한다(최소시간) 이렇게 각 정점과 연결된 간선에 대한 설정을 마치면 다익스트라로 최단경로를 구할 수 있다.나는 vertex[1]을 시작지점, vertex[2]를 도착지점으로 설정해주고 시작하였다. 그.. 더보기 백준 1238 : 파티 https://www.acmicpc.net/problem/1238 단방향 도로이고 목적지 까지 가는 것 뿐 만 아니라 돌아가는 것 까지 계산해야한다는 것이 특징이다. 파티마을로 부터 각각의 마을로 돌아가는것은 파티마을을 시작지점으로 한 다익스트라 한번으로 모두 구할 수 있다. 문제는 각자의 마을에서 파티마을로 가는 최단경로를 구하는 것이다. 1. 각자의 마을을 기준으로 파티마을까지 다익스트라를 N-1번 해준다. - 처음에 이처럼 풀었는데 216ms 로 AC받긴 했다.- 그러나 역시 N-1 번 다익스트라를 한다는 것은 매우 비효율적이다. 2. 단방향의 경로를 역으로 설정해 파티마을을 기준으로 다익스트라 한다. - 이것이 훨씬 나은 해결방법이다. 이 경우 총 다익스트라 2번으로 각 마을에서의 왕복시간을 모두.. 더보기 백준 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; .. 더보기 이전 1 2 3 4 5 6 다음
