Dijkstra5 [백준 - Java] 1238번 : 파티 문제 www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 설명 다익스트라 알고리즘을 이용해 구현하면 된다. 📌 더 자세히 알고 싶다면 아래 포스팅을 참고해주세요 [Java] 다익스트라 (Dijkstra) 최단 경로 알고리즘 하지만 각 구현 방식에 따라 걸리는 시간과 메모리가 천차만별이다. 1. 인접 행렬로 정점과 간선을 표현하고, 기본 다익스트라 알고리즘을 이용해 구현 (2992, 2360 ms) N개의 마을에서 X까지 N번, X에.. 2021. 4. 13. [백준 - Java] 1753번 : 최단경로 문제 www.acmicpc.net/problem/1504www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. www.acmicpc.net 설명 다익스트라 구현 시 인접 행렬을 사용하게 되면 2만 개의 정점에 대해 2만 개 정점으로 가는 간선들을 저장해야 하는데, 간선 하나당 1바이트에 저장한다고 하더라도 4억 바이트, 약 400MB의 메모리를 쓰게 될 뿐 아니라 시간 복잡도 역시 O(V^2)으로 좋지 못하게 된다. 최단 경로 (다익스트라 알고리즘) FAQ 따라서 인.. 2021. 3. 20. [백준 - Java] 1504번 : 특정한 최단 경로 문제 www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 설명 백준 1753번 최단 경로 문제를 응용하면 되는 문제이다. 📌 다익스트라 알고리즘에 대해 더 알고싶다면 아래 포스팅을 참고해주세요! [Java] 다익스트라 (Dijkstra) 최단 경로 알고리즘 전체 코드 import java.util.ArrayList; import java.util.Arrays; import java.util.PriorityQueue; .. 2021. 3. 20. [백준 - Java] 1916번 : 최소비용 구하기 문제 https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 설명 다익스트라 알고리즘을 이용하면 쉽게 풀 수 있는 문제다. 📌 다익스트라 알고리즘에 대해 알고 싶다면 아래 포스팅을 확인해주세요. [Java] 다익스트라 (Dijkstra) 최단 경로 알고리즘 전체 코드 * 무한대를 처음엔 Integer.MAX_VALUE로 했는데 오버플로우가 나는지 채점 중 런타임 에러가 났다ㅠㅠ 무한대 값을 Integer.MAX_VAL.. 2021. 3. 16. [Java] 다익스트라 (Dijkstra) 최단 경로 알고리즘 다익스트라 (Dijkstra) 알고리즘 하나의 시작 정점으로부터 모든 다른 정점까지의 음의 가중치가 없을 때 최단 경로를 찾는 알고리즘 다익스트라 알고리즘에서 음수 간선이 존재하면 안 되는 이유 다익스트라 알고리즘의 각 단계 먼저 집합 S를 시작 정점 v로부터의 최단경로가 이미 발견된 정점들의 집합이라고 하자. 다익스트라 알고리즘에서는 시작 정점에서 집합 S에 있는 정점만을 거쳐서 다른 정점으로 가는 최단거리를 기록하는 배열이 반드시 있어야 한다. 이 1차원 배열을 distance라고 한다. 시작 정점을 v라 한다면 distance[v] = 0이고, 다른 정점에 대한 distance값은 시작 정점과 해당 정점 간의 가중치 값이 된다. 가중치 인접 행렬을 weight라 하면 distance[w] = wei.. 2021. 3. 12. 이전 1 다음 반응형
