Dijkstra

Algorithm/Baekjoon Online Judge
[Java] 백준 1238 (파티) Gold 3
Problem : https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net Approach 단방향 그래프에서 자신에서 출발하여 자신으로 돌아오는 최단거리를 구하는 문제이다. 모든 정점에서의 최단거리를 구하여야 하므로 플로이드-와샬이 쉽게 떠오르겠지만, 이 문제의 입력 최대 크기가 1000이므로 시간복잡도가 O(N^3) 인 플로이드-와샬 알고리즘은 시간초과가 난다. 그래서 다익스트라를 응용하여 문제를 풀이하였다. 마을이 1 ..
→2021.03.30
Algorithm/Baekjoon Online Judge
[java] 백준 10217 (KCM Travel) Gold 1
Problem : https://www.acmicpc.net/problem/10217 10217번: KCM Travel 각고의 노력 끝에 찬민이는 2014 Google Code Jam World Finals에 진출하게 되었다. 구글에서 온 초대장을 받고 기뻐했던 것도 잠시, 찬찬히 읽어보던 찬민이는 중요한 사실을 알아차렸다. 최근의 대세 www.acmicpc.net Approach 이 문제는 다익스트라 알고리즘과 DP를 같이 사용해서 풀어야했다. 인접리스트를 이용하여 그래프를 구성하였으며, 시간순 오름차순(시간이 같으면 비용순 오름차순)으로 구성하였다. 그런 후, 시작점 1부터 다익스트라 알고리즘을(BFS: PriorityQueue 이용) 적용하여, 비용을 초과하지 않는 선에서 모두 갱신해주었다. 다익스..
→2021.01.04
Algorithm/Baekjoon Online Judge
[java] 백준 9370 (미확인 도착지) Gold 2
Problem : https://www.acmicpc.net/problem/9370 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net Approach 다익스트라 알고리즘을 이용하여 푸는 문제이다. 처음 문제를 이해할 때 g나 h로부터 갈 수 있는 노드들을 구하는 문제라고 이해를 했었다. 문제에서 요구한 것을 간단히 쉽게 말하면, 시작점 s에서 임의의 노드 X로 최단거리로 가는 길에 무조건 g-h 혹은 h-g가 있는 노드들을 구하는 것이다. 예를 들어, s = 1, g = 3, h =4 라고 할 때, 1에서..
→2021.01.01
Algorithm/Baekjoon Online Judge
[java] 백준 1504 (특정한 최단 경로) Gold 4
Problem : https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net Approach 가중치가 음수가 아니므로 다익스트라 알고리즘을 이용하여 문제 풀이가 가능하다. 하지만 특정 루트를 반드시 지나가면서 최단거리를 구해야한다. A 부터 B까지 가는 최단경로를 구해야 할 때, V1-V2 경로를 무조건 지나야 한다면, A - V1 - V2 - B A - V2 - V1 - B 위의 두 경로가 존재한다. 따라서 ..
→2021.01.01
Algorithm/Baekjoon Online Judge
[java] 백준 1753 (최단경로) Gold 5
Problem : https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. www.acmicpc.net Approach 최단거리를 구하는 문제이다. 1. 단방향 그래프 2. 가중치는 항상 자연수 위의 조건으로 인해 다익스트라(O(Elog(V))를 이용하여 문제 풀이가 가능하다. 다익스트라 알고리즘은 현재 연결된 노드에서 이어진 모든 곳을 일단 방문하여 거리를 계산하여 저장한 후, 새로운 노드와 새로운 간선들이 추가되면, 도달할수 있는 ..
→2020.12.31
Algorithm/Baekjoon Online Judge
[java] 백준 11779 (최소비용 구하기 2) Gold 3
문제 원문 링크 : https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net Approach 대표적인 Dijkstra 알고리즘을 활용한 문제이다. 문제에서 요구했듯이 최단거리 cost뿐만 아니라 경로 또한 구해야 하므로 최단거리 cost를 업데이트 할 때, 이전 도시가 무엇인지만 별도로 저장해두면 간단하게 구현된다. 이전 노드가 0이라면 그 때의 마을은 시작 마을이 된다. 경로 출력은 Stack 자료형을 이용하면 편하다...
→2020.12.15

• 이전
• 1
• 다음