다익스트라

[프로그래머스 level 3] 가장 먼 노드 (C++)

다익스트라 문제 시작노드는 1번으로 고정되어 있고, 간선 사이의 거리는 항상 1로 고정되어 있다. 일반적인 다익스트라 풀이와 거의 동일하다. 하지만 1번 노드에서 가장 멀리 떨어진 노드의 거리가 최댓값으로 갱신될 때마다 답을 1로 초기화 시켜야 한다. ex 우선순위 큐에 1번 노드가 있다. 가장 먼저 2번 노드에 방문하면 1번 노드와의 최대 거리가 1로 갱신이 되고, 가장 멀리 떨어진 노드의 수는 1이 된다. 그리고 3번 노드에 방문하면 1번 노드와의 거리가 1이므로 현재 최댓값인 1과 동일하다. 따라서 가장 멀리 떨어진 노드의 수는 2로 갱신이 된다. 동일한 방법으로 4, 5, 6번 노드에 방문하면 최대 거리가 2로 갱신이 되고, 가장 멀리 떨어진 노드의 수는 3이 될 것이다. 최종 코드 #includ..

[백준 1486] 등산 (C++)

1486번: 등산 첫째 줄에 산의 세로크기 N과 가로크기 M 그리고, T와 D가 주어진다. N과 M은 25보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 지도가 주어진다. T는 52보다 작거나 같은 자연수이고, D는 1,000 www.acmicpc.net 다익스트라를 사용해서 풀었다. 가로와 세로의 최대 길이가 26으로 짧다. 시작점으로 되돌아와야 한다. 1. 모든 점에 대해서 원점으로 돌아오는 최단거리를 구한다. 우선순위 큐에 들어갈 수 없는 정점은 아래와 같다. 1. 현재 위치의 높이와 다음 위치의 높이 차이가 T보다 크다 2. 다음 정점에 대해서 이미 최단거리가 구해져 있다. 3. 다음 정점으로 가는 거리가 D보다 크다. 4. 다음 정점이 Map을 벗어난다. 위 4가지의 경우에 대해서 con..

[백준 1854] K번째 최단경로 찾기 (C++)

1854번: K번째 최단경로 찾기 첫째 줄에 n, m, k가 주어진다. (1 ≤ n ≤ 1000, 0 ≤ m ≤ 2000000, 1 ≤ k ≤ 100) n과 m은 각각 김 조교가 여행을 고려하고 있는 도시들의 개수와, 도시 간에 존재하는 도로의 수이다. 이어지는 m개의 줄에 www.acmicpc.net 다익스트라 알고리즘을 큰 변형없이 그냥 사용하면 되는 문제이다. 다익스트라 알고리즘에서는 현재까지 구한 시간보다 다음 정점까지 가는데 걸리는 시간이 더 긴 경우에만 다음 정점을 탐색하고, 걸리는 시간을 갱신한다. 따라서 이 조건을 빼는 경우에는 N 정점에 도달하는 경우는 무수히 많아지게 될 것이다. 다익스트라에서는 다음 정점으로 가는 시간이 가장 적은 간선부터 탐색하기 때문에 이를 응용하면, 특정 정점에 ..

[백준 2479] 경로찾기 (C++)

2479번: 경로 찾기 길이가 같은 두 개의 이진수 코드 A와 B가 있다고 하자. 이 두 코드 사이의 해밍 거리는 A와 B의 각 비트를 왼쪽부터 오른쪽으로 차례대로 비교할 때 서로 다른 값을 가진 비트의 수이다. 예를 들 www.acmicpc.net 해밍 거리가 1인 경우만 서로 이동이 가능하다. 따라서 모든 정점을 서로 1:1로 보면서(N^2) 해밍거리를 확인하고 1인 경우에 정점을 연결시켜주는 작업을 가장 먼저 한다. 두 번째로 가장 짧은 해밍 경로를 찾아야 하므로 A부터 B까지 최단경로를 구하는 다익스트라 알고리즘을 수행해 준다. 다익스트라 도중 우선순위 큐에 원소를 넣을 때, 큐에 들어가는 정점에 도달하기 직전의 정점이 현재 정점이므로 parent[next] = now 를 통해 이전 정점을 기록해..

[백준 10217] KCM Travel (C++)

10217번: KCM Travel 각고의 노력 끝에 찬민이는 2014 Google Code Jam World Finals에 진출하게 되었다. 구글에서 온 초대장을 받고 기뻐했던 것도 잠시, 찬찬히 읽어보던 찬민이는 중요한 사실을 알아차렸다. 최근의 대세 www.acmicpc.net 다익스트라, 다이나믹 프로그래밍 [백준 17182] 우주 탐사선 (C++) 17182번: 우주 탐사선 우주 탐사선 ana호는 어떤 행성계를 탐사하기 위해 발사된다. 모든 행성을 탐사하는데 걸리는 최소 시간을 계산하려 한다. 입력으로는 ana호가 탐색할 행성의 개수와 ana호가 hyeo-noo.tistory.com 위 문제와 비슷한 다익스트라+DP문제였다. (주유소_13308 도 비슷하다) 하지만 이번 KCM문제는 최단 시간을 ..

[백준 17835] 면접보는 승범이네 (C++)

17835번: 면접보는 승범이네 첫째 줄에 도시의 수 N(2 ≤ N ≤ 100,000), 도로의 수 M(1 ≤ M ≤ 500,000), 면접장의 수 K(1 ≤ K ≤ N)가 공백을 두고 주어진다. 도시는 1번부터 N번까지의 고유한 번호가 매겨진다. 다음 M개의 줄에 걸쳐 www.acmicpc.net 다익스트라 각각의 도시에서 면접장을 가기위한 다익스트라를 매번 돌려선 안된다. 가상의 도시를 하나 잡고 면접장으로 가는 거리를 0으로 두고 우선순위 큐에 넣어준다. 그리고 면접장에서 시작해 모든 도시로 가는 최단거리를 구한다. 이때 주의할 점은 입력을 받을 때 역방향으로 입력 받아야 한다는 점이다. a -> b가 4 b -> a가 2 이고 면접장이 a라고 하자. b도시에서 면접장을 가는 최소 비용은 2가 되지..

[백준 17182] 우주 탐사선 (C++)

17182번: 우주 탐사선 우주 탐사선 ana호는 어떤 행성계를 탐사하기 위해 발사된다. 모든 행성을 탐사하는데 걸리는 최소 시간을 계산하려 한다. 입력으로는 ana호가 탐색할 행성의 개수와 ana호가 발사되는 행성의 위 www.acmicpc.net 다익스트라, 다이나믹 프로그래밍, 비트마스킹 [백준 13308] 주유소 (C++) 13308번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 수와 도로의 수를 나타내는 정수 N(2 ≤ N ≤ 2,500)과 정수 M(1 ≤ M ≤ 4,000)이 주어진다. 다음 줄에 각 도시 주유소의 리 hyeo-noo.tistory.com 얼마 전 위 문제를 풀면서 다익스트라와 dp를 함께 쓰는 방법에 익숙해진 덕분에 풀 수 있었다 모든 행성이 서로 이..

[백준 14284] 간선 이어가기 2 (C++)

14284번: 간선 이어가기 2 정점 n개, 0개의 간선으로 이루어진 무방향 그래프가 주어진다. 그리고 m개의 가중치 간선의 정보가 있는 간선리스트가 주어진다. 간선리스트에 있는 간선 하나씩 그래프에 추가해 나갈 것이다. www.acmicpc.net 다익스트라 문제를 읽는 순간 s와 t를 연결하는 최소 간선? 하고 바로 스패닝 트리를 돌렸다. 근데 답이 안나온다. 예제 1번도 안나와서 이상해서 다시 읽어봤더니 다익스트라 문제인듯했다.. [백준 2211] 네트워크 복구 C++ 2211번: 네트워크 복구 첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 회선의 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 컴퓨터와 B번 컴퓨터가 통신 시간이 C (1 ≤ C ≤ 10)인 회 hyeo..

[백준 13308] 주유소 (C++)

13308번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 수와 도로의 수를 나타내는 정수 N(2 ≤ N ≤ 2,500)과 정수 M(1 ≤ M ≤ 4,000)이 주어진다. 다음 줄에 각 도시 주유소의 리터당 가격이 도 www.acmicpc.net 다익스트라, 다이나믹 프로그래밍 정점을 지나면서 지금까지 지나온 도시중 리터당 가격이 가장 싼 곳의 가격정보를 들고다니면 된다. 처음에 dist배열을 만들어주지 않고 전체 탐색을 하게해서 메모리초과를 띄웠다. pq에 중복된값이 엄청많이 들어간다고 생각했고 걸러줄 방법이 필요했는데 dp를 사용했다. 현재 정점까지 이동한 비용의 최솟값을 저장하는데 현재 정점에서 가지고 있는 리터당 가격정보도 같이 저장해야한다. dp[현재 정점][리터당 가격의..

[백준 2159] 케익 배달 (C++)

2159번: 케익 배달 첫째 줄에 N이 주어지고 둘째 줄에는 선아가 일하는 레스토랑의 위치가, 셋째 줄부터는 N명의 위치가 X와 Y로 주어진다. 두 좌표 사이에는 공백이 하나 이상 있다. (1 ≤ N, X, Y ≤ 100,000) www.acmicpc.net 다익스트라 주문이 들어온 순서대로 배달한다는 게 문제의 핵심. 별이 시작점이다. 여러 최단거리 중 임의로 하나를 잡으면 위와 같은 경로가 생긴다. 처음에 다익스트라인 줄 모르고 3번 케이크에서 2, 1번 순으로 이동시키며 가장 짧은 거리만 찾아 그리디 하게 탐색할까 생각했었는데 이 문제와는 전혀 어울리지 않는 알고리즘이었다. 현재 위치한 지점의 고객번호와, 지금까지 이동한 거리, 현재 위치를 저장하고 있는 구조체를 만들어주었다. 그리고 일반적인 다익..