다익스트라

[백준 2211] 네트워크 복구 C++

2211번: 네트워크 복구 첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 회선의 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 컴퓨터와 B번 컴퓨터가 통신 시간이 C (1 ≤ C ≤ 10)인 회선으로 연결되어 있다 www.acmicpc.net 다익스트라 최소 스패닝 트리의 탈을 쓴 다익스트라 문제였다. 끊어진 그래프에서 최소 개수의 회선만을 복구해야 한다고 하길래 n-1개의 간선을 연결시켜서 모든 컴퓨터를 연결해 주는 MST 문제로 착각했다. 위 그래프에서 MST는 어떻게 될지 생각해보자 2-3, 2-4, 1-3 간선이 모여서 MST를 이룰 수 있다. 하지만 이 때 1 -> 2로가는 비용은 5가 되고, 1 -> 4로 가는 비용은 7이 된다. 각각 기존의 최단거리였던 4, 3..

[백준 16681] 등산 C++

16681번: 등산 첫 번째 줄에 지도에 표시된 지점의 개수, 지점을 잇는 경로의 개수, 주환이의 거리 비례 체력 소모량, 높이 비례 성취감 획득량을 나타내는 정수 N, M, D, E가 공백을 사이에 두고 주어진다. (2 ≤ www.acmicpc.net 다익스트라 시작점은 항상 1이고 도착점은 항상 N이다. 시작점에서 도착점으로 가면서 높이가 점점 높아지는 최단거리 다익스트라를 수행한다. 도착점에서 시작점으로 가면서 높이가 점점 높아지는 최단거리 다익스트라를 수행한다. 임의의 가운데 정점을 잡고 해당 정점이 시작점과 도착점 모두와 연결되어있다면 위 2개의 다익스트라를 통해서 시작점과 연결된 최단거리는 자연스럽게 높이가 증가하는 최단거리가 구해지고, 임의의 정점에서 도착점으로 가는 최단거리는 높이가 감소하..

[백준 1504] 특정한 최단경로 C++

1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 다익스트라 1. 문제 해결 아이디어 반드시 방문해야 하는 정점이 2개 주어진다. 예를 들어 1번 정점에서 4번 정점으로 가야하는데 2, 3번 정점을 반드시 거쳐야 한다고 하자 첫 번째로 1 -> 2 -> 3 -> 4 순으로 정점을 방문할 수 있다. 위 순서는 각 정점이 방문된 시점을 순서대로 나열한 것에 불과하다. 1에서 2, 2에서 3, 3에서 4로 가는 최단 거리를 구하기 위해서 중간에 다양한 정점을 방문할 수 있..

소방차 (FIRETRUCKS)

algospot.com :: FIRETRUCKS 소방차 문제 정보 문제 한겨울 날씨가 추워지면 각종 난방 기구 때문에 화재가 발생하기 쉽습니다. 어느 추운 겨울날 서울 시내 n개의 지역에 동시에 화재가 발생했습니다. 피해를 최소화하기 www.algospot.com 다익스트라 문제 설명 더보기 각 소방서마다 불이나는 집까지의 최단거리를 구하고, 그 중에서 가장 가까운 소방서만 선택해서 전체 시간을 구한다면 시간초과가 날 것이다. Key point는 소방서가 시작점이기 때문에 가상의 정점(0번 정점)을 만들고, 0번 정점에서 소방서까지 가는 비용을 0으로 잡고 queue에 넣어주면 된다! -> 0번 정점에서 모든 소방서로 가중치가 0인 간선을 연결한다고 생각하자 우선순위 큐에서 항상 가장 적은 시간이 소요되..

[백준 11779] 최소 비용 구하기 2 C++

11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 다익스트라 1. 문제 해결 아이디어 A 도시에서 B 도시로 가는 최소 비용을 알아야 한다. 간선의 비용은 음수가 없다. 위 두가지 정보로 다익스트라문제인걸 알았다. 다익스트라 알고리즘에 의해서 도착점을 발견하면 현재 가지고 있는 최소 비용이 도착점 까지의 비용이된다. bfs를 수행하면서 현재 정점에 도달하기 직전에 거쳐온 정점을 저장해둔다. 예시 입력을 그래프로 나타냈다. 1이 시작점이고 우선순위 큐에 의해서 queue에 4, 2,..

[백준 1238] 파티 C++

1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 다익스트라 1. 문제 해결 아이디어 단순한 다익스트라 문제는 A->B까지 가는 거리의 최단거리를 구하는 것이지만 이 문제는 A->X로가는 최단거리 + X->A로 되돌아오는 최단거리를 구해야 한다. A->X로 가는 최단거리를 구해보자. 정점의 개수가 최대 1000개, 간선의 개수가 최대 10000개 이므로 O(|V||E|) = 10,000,000 이 되어 시간내에 풀 수 있다고 생각했다. 그래서 A->X로 가는 최단거리를 A의 개수만..