다익스트라 개념을 잘 모른다면 아래 포스팅을 읽고 오자. https://myeongju00.tistory.com/52 [Algorithm] Java - 다익스트라(Dijkstra) 알고리즘 다익스트라 알고리즘이란? BFS와 DP를 활용한 최단경로 탐색 알고리즘이다. 즉, 그래프에서 출발점에서 목표점까지의 최단거리를 구할 때 사용하는 알고리즘이다. 이 과정에서 도착 정점 뿐만 아 myeongju00.tistory.com 구현에는 인접 행렬 방식, 우선순위 큐 방식이 있다. 노드의 개수를 V라고 할 때 인접 행렬 방식은 O( V^2 ) 우선순위 큐 방식은 O( V log V ) 의 시간 복잡도를 가진다. 따라서 알고리즘 문제풀이 시 우선순위 큐 방식을 주로 사용한다. 인접 행렬 방식 1..

다익스트라 알고리즘이란? BFS와 DP를 활용한 최단경로 탐색 알고리즘이다. 즉, 그래프에서 출발점에서 목표점까지의 최단거리를 구할 때 사용하는 알고리즘이다. 이 과정에서 도착 정점 뿐만 아니라 모든 다른 정점까지 최단 경로로 방문하며 각 정점까지의 최단 경로를 모두 찾게 된다. 매번 최단 경로의 정점을 선택해 탐색을 반복하는 것이다. ❓왜 다이나믹 프로그래밍일까? 하나의 최단 거리를 구할 때 그 이전까지 구했던 최단 거리 정보를 그대로 사용하기 때문이다. 다익스트라 알고리즘 특징 그래프 내부 하나의 정점(노드, Vertex)에서 다른 모든 정점으로 가는 최단 경로를 알려줌 그래프의 간선(Edge)마다 가중치가 존재할 때 사용 ⇒ BFS를 활용한 최단 경로 구하기와 다른 점 간선의 음의 가중치는 존재하지..