다익스트라 알고리즘이번 포스트에서는 가중치가 있는 그래프에서 한 시작점으로부터 모든 정점까지의 최단 거리를 구하는 알고리즘인 다익스트라 알고리즘을 알아보겠습니다. 단순한 BFS나 DFS로는 가중치가 있는 그래프의 최단 경로를 구하기 어렵지만 다익스트라 알고리즘은 우선순위 큐를 활용해 최적화된 방식으로 해결할 수 있습니다.다익스트라 알고리즘이란?특정 시작점에서 모든 정점까지의 최단 거리를 계산하는 알고리즘입니다.그래프의 간선 가중치가 음수가 아닌 경우에만 사용 가능합니다.음수 간선이 존재하면 이후에 더 짧은 경로가 나타날 수 있으므로 벨만-포드(Bellman-Ford) 알고리즘을 사용해야 합니다.우선순위 큐(Priority Queue)를 활용하여 구현할 수 있으며 시간 복잡도는 O((V + E) log V..

너비우선탐색(BFS)이번 포스트에서는 그래프 탐색 알고리즘 중 하나인 너비우선탐색(BFS)에 대해서 알아보겠습니다.너비우선탐색(BFS)이란?시작 정점에서 가까운 정점부터 차례대로 탐색하는 알고리즘즉, 먼저 방문한 정점의 이웃 노드들을 모두 탐색한 뒤 레벨별로 넘어갑니다.주로 같은 가중치를 가진 그래프에서 최단거리 알고리즘으로 쓰입니다.수도 코드(Pseudo Code)u: 탐색 시작 정점visited[]: 각 정점의 방문 여부를 저장하는 배열 (중복 방문 방지)Q: 탐색할 정점을 순서대로 담아두는 큐 (FIFO 구조)v: 현재 큐에서 꺼낸 정점w: 현재 정점 v의 인접 정점들BFS(u): visited[u] ← true // 시작 정점 u 방문 표시 Q ← e..