devbelly

문제 https://www.acmicpc.net/problem/5917 알고리즘 Dijkstra 풀이 최단거리 중 하나의 간선의 값을 두배로 하였을 때의 최댓값을 구하는 문제입니다. 다익스트라임은 최단거리임을 보고 알 수 있습니다. 문제 제한은 $N$이 100 이하, $M$은 10000 이하입니다. 단순한 접근으로는 $M$의 간선들을 하나씩 두배로 만든 후 그때마다 새로이 다익스트라를 사용하는 것입니다. 하지만 $M$제한이 10000이므로 이 방법은 무리가 있습니다. 이 방법에는 불필요한 부분이 있습니다. 바로 최단거리에 포함되지 않는 간선들 또한 두 배로 바꾸는 것입니다. 이는 아무런 의미가 없는 행동입니다. $N$개로 이루어진 노드에서 최단거리는 최대 $N-1$개의 간선을 통해 이루어져 있습니다. 즉..

문제 https://www.acmicpc.net/problem/10652 알고리즘 Dijkstra, BFS 풀이 Bessie와 Elsie가 돌아다닐때 드는 에너지와 Piggy Back 상태에서 드는 에너지가 주어졌을 때, $N$까지 도달하기 위한 최소에너지는 구하는 문제입니다. 3인통화 문제와 굉장히 유사합니다. 도착지도 하나의 소처럼 취급을 하여 세 마리의 소에서 각각 다익스트라를 사용하면 문제가 해결됩니다. 다만, 각 소마다 그래프를 이동할 때 드는 비용은 동일하므로 다익스트라 대신 BFS를 사용하면 더 빠르게 문제를 풀 수 있습니다. 코드 #include #define rep(i, n) for (int i = 0; i < n; ++i) #define REP(i, n) for (int i = 1; i..

문제 www.acmicpc.net/problem/20968 알고리즘 Dijkstra 풀이 소의 품종마다 서로 연락할 수 있는 관계가 주어졌을 때, 첫 번째 소가 맨 마지막 소에게 메시지를 전달하기 위한 최솟값을 구하는 문제입니다. 일반적으로 PQ를 이용한 다익스트라의 시간복잡도는 $O(ElogV)$입니다. 문제에서 $N$제한이 50000이므로 무작정 다익스트라를 사용하게 되면 시간 초과를 받게 됩니다. 빨간색 원이 현재 PQ에서 꺼낸 소라고 하겠습니다. 녹색은 빨간색 품종이 연락할 수 있는 품종을 의미합니다. 만일 위와 같이 녹색품종들이 모두 빨간색에서 메시지를 받을 수 있다면 굳이 첫 번째를 제외한 2, 3, 4번째들을 검사할 필요는 없습니다. 즉 현재 소에서 연락 가능한 품종들마다 가장 가까이 있는 ..

문제 www.acmicpc.net/problem/2398 알고리즘 Dijkstra 풀이 세명이 통화를 하기 위해 간선들을 연결하기 위한 최소비용, 그 때 사용하는 간선들을 출력하는 문제입니다. 사람들이 그래프 위에서 움직여 최적의 장소에서 모이는 문제로 해석해보겠습니다. 각 사람마다 각 노드마다의 최소거리를 알 수 있다면 즉, 한 지점마다 세 사람의 최소거리를 안다면 우리는 어디 지점에서 세 사람이 만나야 하는지 알 수 있습니다. 사람마다 다익스트라를 돌려 총 세번의 다익스트라를 수행하고 그때마다 그 사람이 어디 노드에서 어디 노드로 갔는지를 기록하면 됩니다. 코드 #include #define rep(i, n) for (int i = 0; i < n; ++i) #define REP(i, n) for (..

문제 www.acmicpc.net/problem/2276 알고리즘 다익스트라 풀이 $N X M $ 격자판에 표면의 높이들이 주어질 때, 채울 수 있는 최대 물의 높이를 구하는 문제입니다. 격자판의 밖에서 격자판으로 물이 스며가는 형태로 구현을 했습니다. 즉 다익스트라의 시작점은 격자판의 테두리 부분이고 도착점은 테두리를 제외한 칸이라고 생각할 수 있습니다. 다익스트라는 하나의 시작점으로부터 하나의 도착지를 구하는 알고리즘이라 이를 적용하려면 약간의 테크닉을 써야합니다. A개의 시작점과 B개의 도착점이 주어졌다면, A개의 시작점들의 조상 시작점과 B개의 도착점들의 조상 도착점을 하나씩 만드는 것입니다. 아래코드에서는 각각 i*j, i*j+1로 사용하였습니다. 그리고 모든 격자판을 연결하는데, 높이가 높은 ..