본문 바로가기

다익스트라

BOJ)13213 Binary Roads 문제: icpc.me/13213 N개의 정점과 E개의 간선으로 이루어진 그래프에서 0번정점에서 N-1번 정점으로의 최단거리를 구하는 문제이다. 단, 조건이 하나있는데 엣지에 패리티가 붙어있어서 0이나 1중 하나의 속성을 지닌다. 이전에 0인 엣지를 통하여 왔다면 다음에는 1인 엣지만 밟을 수 있다. 이 문제를 해결하기 위하여 각 정점을 2차원으로 생각해주면 된다. 0인 엣지를 밟고 V번 정점인 경우와 1인 엣지를 밟고 V번 정점인 경우로 나눠서 생각해주면 다익스트라를 2번 실행하는 것으로 문제를 해결해 줄 수 있다. N제한이 크긴 하지만 시간이 3초이니 제한시간 내에는 넉넉히 들어올 수 있다. 12345678910111213141516171819202122232425262728293031323334353.. 더보기
BOJ)5542 JOI 국가의 행사 문제: icpc.me/5542 쿼리에서 받는 두 도시간의 경로 중 경로에 포함 된 도시들의 축제하는 도시와의 떨어진 거리의 값들 중 최솟값이 최대가 되는 경로를 구하는 문제이다. 우선 다익스트라 알고리즘을 사용하여 각 정점들의 가중치(축제가 열리는 도시와의 최단거리)를 구해줄 수 있다. 이후 쿼리를 처리해주어야 하는데 disjoint set을 이용하여 쿼리를 처리해주려고 한다. 우선 각 쿼리 번호에 해당되는 양 끝 정점들에 쿼리 번호들을 저장해준 뒤 간선의 가중치가 큰 순서대로 간선을 정렬하여 간선을 보면서 정점을 dsu를 이용하여 병합해 줄것이다. 이 때 만약 두 정점이 같은 쿼리 번호를 가지고 있다면 해당 쿼리 번호의 답은 그 간선의 가중치가 될 것이다. 1234567891011121314151617.. 더보기
BOJ)1445 일요일 아침의 데이트 문제: icpc.me/1445 꽃을 통과하는 경우를 최소로 하고 싶고 꽃을 통과하는 경우의 최소가 여러경로가 존재할 때 꽃의 옆을 지나가는 경우를 최소로 하고 싶을 때 최단경로를 찾는 문제이다. 우선이 되는 꽃을 통과하는 경우에 나올 수 있는 최대 꽃의 수 2500보다 큰값을 곱해서 cost를 주고 꽃의 옆을 지나가는 경우를 1로 준 뒤 다익스트라를 돌린 후 곱한 값을 나눈 값과 나머지를 출력해주면 된다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758#include #include #include #include using namespace std;int n,.. 더보기
다익스트라 알고리즘(Dijkstra's Algorithm) 다익스트라 알고리즘은 간선에 가중치가 있는 그래프에서 1:N 최단거리를 구하는 알고리즘 입니다. 여기서 말하는 1:N이란 한 정점 V를 기준으로 V와 같은 컴포넌트에 속해있는 모든 정점들과의 최단거리를 계산한다는 의미입니다. 보통 가중치가 없는 그래프에서의 1:N 최단거리는 BFS (O(V+E))를 통하여 계산해주고, 가중치가 있는 그래프에서의 N:N 최단거리는 플로이드 워셜(O(N^3))으로 계산해주는게 일반적입니다. 단 다익스트라를 포함한 위에서 제시한 알고리즘들은 가중치가 음수 일때는 사용하지 못합니다. 가중치가 음수일 경우 벨만포드 알고리즘(O(VE))이나 SPFA(O(VE))를 통하여 최단거리를 구해주어야 합니다. 그렇다면 다익스트라는 어떤 방식으로 1:N 최단거리를 구해낼까요? 일단 다익스트라.. 더보기
BOJ)13308 주유소 문제: icpc.me/13308 1->n까지의 최소 비용을 원하는 문제이므로 다익스트라로 해결해줄 수 있다. 다만 문제에서 비용과 거리가 동시에 존재하므로 현재 보는 경로상에서 정점 x까지 순회하는 동안 발견한 가장 저렴한 주유소의 주유가격을 저장하여 d[here][mincost]로 2차원 테이블을 잡아 문제를 해결해주어야 한다. 1234567891011121314151617181920212223242526272829303132333435363738394041#include #include #include #include #include using namespace std;typedef long long ll;vector vt;ll n, m, l[2550], x, y, z, d[2550][2550], r.. 더보기
BOJ)1326 폴짝폴짝 문제: icpc.me/1326 각 징검다리에 숫자가 써있고 해당 징검다리에서는 숫자의 배수만큼 떨어져 있는 징검다리까지 점프 할 수 있을때 a에서 b까지 의 최단거리를 출력하는 문제이다. 해당 징검다리에서 갈 수 있는 모든 징검다리까지 cost가 1인 간선을 연결해주고 다익스트라를 이용하여 최단거리를 구해줄 수 있다. 이 때 주의할 점은 배수 이기 때문에 나보다 작은 지점으로도 점프할 수 있다. 12345678910111213141516171819202122232425262728293031323334353637#include #include #include #include #include using namespace std;int n, a[10001], s, e, dp[10001];vector vt;in.. 더보기
BOJ)9370 미확인 도착지 문제:icpc.me/9370 시작지점이 주어지고 이들의 도착 예정 경로들이 주어진다. 이 때 주어진 도착 예정 경로로는 무조건 최단경로로 이동할 때 어떤 한 간선을 통과하는지 여부를 묻는 문제이다. 우리는 시작지점에서 다익스트라를 실행하여 모든 정점으로의 최단거리를 전부 계산해준 뒤 주어진 간선에서 부터 다시 다익스트라를 실행하여 주어진 간선에서 부터의 최단 거리를 구해준다. 그리고 나서 도착 예정경로중 (시작정점에서 도착 예상 정점의 최단거리 = 시작정점에서 주어진 간선까지의 최단거리 + 주어진간선부터 도착 예상정점으로의 최단거리) 인 정점들을 출력해주면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344.. 더보기
BOJ)12026 BOJ 거리 문제:icpc.me/12026 B->O->J->B 로 이동가능한 경로를 n^2 으로 전부 간선을 연결해 준 뒤 다익스트라 알고리즘을 이용하여 최단거리를 구해주면 된다. 12345678910111213141516171819202122232425262728293031323334353637383940#include #include #include #include #include #include #include using namespace std;int n, dp[1001];string a;vector vt;int main() { memset(dp, -1, sizeof(dp)); scanf("%d", &n); vt.resize(n + 1); cin >> a; for (int i = 0; i 더보기
BOJ)14226 이모티콘 문제: icpc.me/14226 이모티콘에 대한 연산이 주어질 때 이모티콘 S개를 치기 위해 필요한 시간의 최솟값을 구하는 문제이다. 화면에 존재하는 이모티콘을 복사해서 붙여넣는 경우는 2의 시간이 이모티콘 하나를 삭제하는 경우는 1의 시간이 걸린다 생각하고 다익스트라를 돌렸는데 WA를 계속 받았다. 문제 조건을 잘 확인해보니 한번 복사한 이모티콘을 여러번 붙여넣을 수 있는 것같았다. 그래서 다익스트라에서 pq의 3번째 인자로 붙여넣었을 경우의 붙여넣은 수를 인자로 주어 붙여넣기 하였을 경우 다시 붙여넣을 수 있게 소스를 수정하여 맞았다. 12345678910111213141516171819202122232425262728293031#include #include #include #include usin.. 더보기
BOJ)14431 소수마을 문제: icpc.me/14431 마을의 좌표가 주어질 때 두 좌표사이의 거리의 정수부분이 소수일 경우에만 이동가능한다는 조건하에 소수마을에서 A마을로 이동하는데 걸리는 최단경로를 구하는 문제이다. 에라토스테네스의 체를 이용하여 소수들을 구해준 후 거리가 소수인 정점들을 서로 간선 연결을 해준 뒤 다익스트라를 돌려서 해결하면 된다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354#include #include #include #include #include using namespace std;int getdist(pair a, pair b) { return sqrt((a.fir.. 더보기