다익스트라

문제 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이다익스트라무지와 어피치가 S에서 경유지 I까지 같이 이동한다. 무지와 어피치가 따로 A, B로 이동한다. 한명은 I에서 A로, 한명은 I에서 B로 이동한다.즉, 최소 거리는 S -> I, I -> A, I -> B, 세 경로의 합의 최솟값이다. S, A, B 세 노드에서 다른 노드로의 최소 거리만 있으면 문제를 풀 수 있다.현재 그래프는 양방향 경로이기 때문에, 다익스트라는 S, A, B 총 세 번만 실시해도 문제를 풀 수 있다.코드#include #include #include #include #incl..

문제 5719번: 거의 최단 경로 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있 www.acmicpc.net 풀이 다익스트라 문제이다. 다익스트라를 한번 실시하고, 최단 경로를 제거한 다음, 다시 다익스트라를 한번 실시하는 방식으로 풀어야 한다. 처음에는 최단 경로를 모두 제거될 때까지 반복해서 다익스트라를 실시 -> 경로 제거를 실시하였다. 이렇게 계속해서 다익스트라를 실시하면 시간초과가 발생한다. 한번의 다익스트라로 최단 경로를 모두 표시할 수 있도록 path 배열을 사용하였다. if (next_dist < dist[next_no..

문제 1854번: K번째 최단경로 찾기 첫째 줄에 $n$, $m$, $k$가 주어진다. ($1 ≤ n ≤ 1\,000$, $0 ≤ m ≤ 2\,000\,000$, $1 ≤ k ≤ 100$) $n$과 $m$은 각각 김 조교가 여행을 고려하고 있는 도시들의 개수와, 도시 간에 존재하는 도로의 수이다. 이 www.acmicpc.net 풀이 다익스트라, 우선순위 큐 문제이다. 처음에는 특정 노드에 도착할 때마다 벡터에 현재 비용을 추가하는 방식으로 접근했다. 하지만 이렇게 하면, 특정 노드에는 k번 도달하지 않고 다익스트라가 종료될 수 있다. 그렇다고, 노드에 도착할 때마다 다익스트라를 돌리는 우선순위 큐에 값을 추가하면 다익스트라가 끝나지 않는다. 다익스트라에 추가적으로 우선순위 큐(내림차순)를 추가하여 풀 ..

문제 2211번: 네트워크 복구 첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 회선의 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 컴퓨터와 B번 컴퓨터가 통신 시간이 C (1 ≤ C ≤ 10)인 회선으로 연결되어 있다 www.acmicpc.net 풀이 다익스트라에 경로 추적을 결합한 문제이다. 처음 문제를 읽었을 때, 최소 스패닝 트리 문제인줄 알았지만 최소 스패닝 트리로 접근할 경우 문제의 두번째 조건이 만족하지 않는다는 것을 알았다. 최소 스패닝 트리로 네트워크를 만들었을 때는 그래프의 가중치의 합이 최소인 그래프가 만들어지지, 최단 경로로 그래프를 만들어 주지는 않을 수 있다. 그러므로, 다익스트라로 접근하였고 필요한 것은 최단 거리가 아니라 연결된 간선이 필요하므로..

문제 1719번: 택배 명우기업은 2008년부터 택배 사업을 새로이 시작하기로 하였다. 우선 택배 화물을 모아서 처리하는 집하장을 몇 개 마련했지만, 택배 화물이 각 집하장들 사이를 오갈 때 어떤 경로를 거쳐야 하 www.acmicpc.net 풀이 다익스트라에 경로 추적을 결합한 문제이다. 출력 시, 각 집하장에서 다른 집하장까지의 최단 경로가 필요하므로 각 집하장마다 다익스트라를 실행해야 한다. 다익스트라 도중에 최단 경로가 갱신될 때, 현재 노드의 부모 노드를 갱신한다. next_node를 최단 경로로 도달하기 위해서는 current_node애서부터 와야 한다. 부모 노드를 추적하면 한 집하장에서 다른 집하장으로 최단 경로로 갈 때, 바로 다음 집하장을 알 수 있다. 코드 #include #inclu..

문제 1446번: 지름길 첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하인 양의 정수이고, D는 10,000보다 작거나 같은 자연수이다. 다음 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이 www.acmicpc.net 풀이 다익스트라 문제이다. 도로를 하나의 그래프로 생각하는데 주목한다. 그래프의 노드는 바로 다음 노드와 거리가 1로 연결되어 있다. 위의 그래프에서 입력 받은 지름길을 추가한다. 역주행 할 수 없으므로, 지름길의 끝이 D를 넘어간다면 그래프에 추가하지 않는다. 지름길의 거리가 시작과 끝의 거리보다 길다면, 거리를 줄일 수 없으므로 그래프에 추가하지 않는다. 그래프를 0에서부터 다익스트라를 통해 D까지의 최소 거리를 구한다. 코드 #include..

문제 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net 풀이 다익스트라 문제이다. 첫 시도에는 s를 시작점으로 다익스트라를 한번 실시하고, 경로를 추적하여 시도하였지만, 메모리 초과가 발생하였다. 그리고 이 방법은 x까지의 최단 경로가 여러 개 존재할 경우, 답이 올바르지 않을 수 있다. s, g, h를 시작점으로 다익스트라를 세번 실시한다. s -> g -> h -> x로 가는 최단 경로의 비용이 s -> x로 가는 최소 경로의 비용과 일치한다면, 해당 최소 경로는 g -> h를 거친다고 볼 수 있다. ..

문제 10282번: 해킹 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 www.acmicpc.net 풀이 다익스트라 문제이다. b가 감염되고 s초 후, a가 감염된다는 뜻은, 노드 b에서 노드 a로 가는 간선의 비용이 s라는 뜻이다. 위의 조건대로 그래프를 만들고 c를 시작으로 다익스트라를 실시한다. c에서 갈 수 있는 컴퓨터의 수와 최대 거리를 구한다. 코드 #include #include #include #include #include using namespace std; vector edges; vector dist; void solution(int st..

문제 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 풀이 [백준][C++] 1261: 알고스팟 문제 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의 kantatatam.tistory.com 너비 우선 탐색 문제로, 위의 문제와 풀이가 동일하다. 하나 주의해야 할 점은, 시작 지점의 거리가 0이 아니고, 시작 지점의 도둑 루피..

문제 풀이 다익스트라 알고리즘에 경로 추적을 추가한 문제이다. 다익스트라 알고리즘 도중 최단 경로가 갱신되면 노드의 부모 노드를 교체한 방식으로 진행한다. next_node에 최단 경로로 도달하기 위해서는 current_node에서 와야 한다. 코드 #include #include #include #include using namespace std; int n, m; int start_node, end_node; vector graph; int dist[1001][1001]; int parent[1001]; vector path; void dijkstra(int n) { dist[n][n] = 0; parent[n] = n; priority_queue pq; pq.push(make_pair(0, n));..