승형님의 블로그

https://www.acmicpc.net/problem/1854 1854번: K번째 최단경로 찾기 첫째 줄에 n, m, k가 주어진다. (1 ≤ n ≤ 1000, 0 ≤ m ≤ 2000000, 1 ≤ k ≤ 100) n과 m은 각각 김 조교가 여행을 고려하고 있는 도시들의 개수와, 도시 간에 존재하는 도로의 수이다. 이어지는 m개의 줄에 www.acmicpc.net 요약 한 정점에서 임의의 정점으로 향하는 K번째 최단경로를 구한다. 1. N개의 도시와 M개의 도로로 이루어진 가중치 방향 그래프가 주어진다. 2. 다익스트라 알고리즘의 아이디어와 우선순위 큐를 활용하여 풀이한다. 3. 기존의 다익스트라 알고리즘에서는 오직 1번째 최단경로만이 중요하므로 한 정점을 방문했을 때의 값이 dist[vertex] ..

https://www.acmicpc.net/problem/11562 11562번: 백양로 브레이크 서울 소재 Y모 대학교에서 대규모 공사를 진행하면서, 학교가 마치 미로처럼 변해버리고 말았다. 공사 이전까지는 어떤 건물에서 출발하더라도 다른 모든 건물로 갈 수 있는 길이 있었으나, 공 www.acmicpc.net 요약 임의의 두 정점간의 최단거리를 묻는 K개의 쿼리를 처리한다. 1. 초기의 학교의 상태가 주어진다. 이때, 일방통행 도로를 1번의 조작을 통해 양방향 도로로 바꿀 수 있다. 따라서, 양방향 도로의 경우에는 가중치가 0이고 일방통행 도로인 경우에는 순방향일때 가중치가 0, 역방향일때 가중치가 1인 가중치 방향 그래프로 바꾸어 생각할 수 있다. 2. 임의의 정점 S와 E간의 최단거리를 묻는 K개..

https://www.acmicpc.net/problem/2307 2307번: 도로검문 그림 1은 어떤 도시의 주요 지점과 그 지점들 간의 이동시간을 나타낸 그래프이다. 그래프의 노드는 주요 지점을 나타내고 두 지점을 연결한 도로(에지)에 표시된 수는 그 도로로 이동할 때 걸 www.acmicpc.net 요약 간선 하나를 제거하여 1번 정점에서 N번 정점으로 가는 최단경로를 최대로 만든다. 1. 도시의 주요 지점 N개와 도로 M개로 이루어진 가중치 무방향 그래프가 주어진다. 2. 우선, 지연시킬 수 있는 최대 시간은 (간선 제거 후 최단경로) - (간선 제거 전 최단경로)이므로, 다익스트라를 통해 간선 제거 전 최단경로를 구한다. 3. 간선을 하나 제거하여 최단경로를 변경시키기 위해서는 제거하는 간선이 ..

https://www.acmicpc.net/problem/1162 1162번: 도로포장 첫 줄에는 도시의 수 N(1 ≤ N ≤ 10,000)과 도로의 수 M(1 ≤ M ≤ 50,000)과 포장할 도로의 수 K(1 ≤ K ≤ 20)가 공백으로 구분되어 주어진다. M개의 줄에 대해 도로가 연결하는 두 도시와 도로를 통과하 www.acmicpc.net 요약 1번 정점에서 N번 정점으로 이동할 때 최대 K개의 가중치를 무시하여 최단경로를 찾는다. 1. N개의 도시와 M개의 양방향 도로로 이루어진 가중치 무방향 그래프가 주어진다. 2. 도로를 포장하는 경우에는 도로의 가중치가 0이 되고, 최대 K개의 도로를 포장할 수 있을 때의 최단경로는 다익스트라와 DP를 활용하여 구할 수 있다. 3. dist[i][j] 배열..

https://www.acmicpc.net/problem/5719 5719번: 거의 최단 경로 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있 www.acmicpc.net 요약 정점 S에서 정점 D로 가는 최단경로에 포함되지 않은 도로로만 이루어진 그 다음 최단경로를 구한다. 1. 가중치가 존재하는 단방향 그래프가 주어진다. 2. 다익스트라를 통해 최단경로와 그 경로를 역추적하여 저장한다. https://int-p.tistory.com/13 다익스트라(Dijkstra) 알고리즘과 최단경로 역추적 다익스트라 알고리즘을 활용하여 최단경로를..

https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 요약 정점 S에서 정점 E로 가는 최단경로의 길이와 그 경로를 구한다. 1. A번째 도시와 B번째 도시를 단방향으로 연결하는 버스를 가중치 방향 그래프로 생각할 수 있다. 2. 다익스트라를 통해 최단경로의 길이를 구하고, 그 과정에서 최단경로를 역추적한다. https://int-p.tistory.com/13 다익스트라(Dijkstra) 알고리즘과 최단경로 역추적 다..