🔻다익스트라 알고리즘(Dijikstra's Algorithm) 다익스트라 알고리즘이란 가중치 그래프에서 한 정점으로부터 모든 정점의 최단거리를 구하는 알고리즘이다. 다익스트라의 경우 가중치에 음수가 존재하면 안된다는 제약사항이 존재한다. 🔶다익스트라 알고리즘의 원리 다익스트라 알고리즘의 기본적인 원리는 굉장히 간단하다. 두가지 작업을 모든 정점을 모두 방문할 때까지 반복하는 것이다. 1. 방문하지 않은 정점 중 가장 cost가 작은 정점을 방문한다. 2. 해당 정점과 연결된 정정들 중에서 거리가 이전에 기록한 값보다 작다면 값을 갱신한다 이 두작업을 무한 반복하는 것인데, 글로만 보면 무슨 말인지 이해하기 힘들 수 있으니 그림을 통해 알아보자. 6개의 정점이 있고 각 정점사이의 cost가 그림과 같은 그..

🔻그래프 탐색 알고리즘 이번에는 그래프를 탐색하는 알고리즘에 대하여 다루어 볼 것이다. 그래프 탐색 알고리즘이란 한 정점에서 시작하여 차례대로 그래프에 있는 모든 정점들은 한번씩 방문하는 알고리즘을 뜻한다. 많은 그래프에 대한 문제를 해결하기 위해서 그래프 탐색 알고리즘을 알아야하는데 예를들어 다음과 같은 상황에서 탐색이 필요하다. 한 정점과 다른 정점의 경로를 구할 때 그래프가 연결되어 있는지 확인할 때 신장 트리(Spanning Tree)를 찾을 때 그래프를 탐색하는 알고리즘은 굉장히 중요한 알고리즘이라고 들었다. 알고리즘 사이트인 프로그래머스에서 보았을 때도 그래프 탐색이 출제 빈도수도 높고 정답률이 낮게 나온다. 대표적으로 깊이 우선 탐색(Depth-First Search)과 너비 우선 탐색(Br..