밤이 블로그

BOJ#4485 녹색 옷 입은 애가 젤다지? * 문제https://www.acmicpc.net/problem/4485 * 풀이다익스트라 (Priority Queue 이용)개념만 알면 풀 수 있는 기본 문제이므로 설명은 생략합니다. * 나의 코드 https://github.com/stack07142/BOJ/blob/7abd485c7bdc3853570ff8d262afbd03b7234709/BOJ%234485/src/Main.java import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.PriorityQueue; import java.util.StringTokenize..

벨만-포드 알고리즘(Bellman-Ford algorithm) 최단 경로 알고리즘에서 대표적인 것으로는 1) 다익스트라 : 유향그래프, 한점 - 다수의 점, 음수 가중치 X2) 벨만-포드 : 유향그래프, 한점 - 다수의 점, 음수 가중치 O, 음수 사이클 X3) 플로이드-와샬 : 모든 점- 모든 점 여기서는 벨만-포드 알고리즘에 대해 알아보겠습니다. * 벨만-포드 알고리즘(Bellman-Ford algorithm) 벨만-포드 알고리즘은 가중 유향 그래프에서 최단 경로 문제를 푸는 알고리즘이다. 이때 변의 가중치는 음수일 수도 있다. 다익스트라 알고리즘은 벨먼-포드 알고리즘과 동일한 작업을 수행하고 실행 속도도 더 빠르다. 하지만 다익스트라 알고리즘은 가중치가 음수인 경우에는 처리할 수 없으므로, 이런 경..