BFS (3) 썸네일형 리스트형 120. Dial's Algorithm 다이얼 알고리즘(Dial's Algorithm)은 간선들의 가중치가 크지 않은 그래프에서 최단 경로를 구할 때 사용할 수 있는 알고리즘으로, $0$-$1$ BFS의 발전된 버전이라고 생각할 수도 있다. 각각의 간선의 가중치가 $0$ 이상 $c$ 이하의 정수일 때 다이얼 알고리즘은 $(c+1)$개의 큐를 사용하여 최단 경로를 구한다. 큐 대신 스택, 벡터 등을 사용할 수도 있다. $c = 1$일 경우 $0$-$1$ BFS와 매우 유사한 형태가 되며, $2$개의 큐를 하나의 덱으로 바꾸면 $0$-$1$ BFS와 같아진다. 다이얼 알고리즘의 작동 방식은 다음과 같다. 1. 시작 정점은 $k$, 정점 $k$로부터 정점 $i$까지의 최단 경로를 $d_i$라고 한다. 2. 정점 $x$에서 정점 $y$로 .. 119. 0-1 BFS $0$-$1$ BFS는 모든 간선의 가중치가 $0$ 또는 $1$인 그래프에서 사용할 수 있는 최단 경로 알고리즘으로, 한 정점에서 다른 정점들까지의 최단 경로를 구한다. 작동 방식은 다음과 같다. 1. 시작 정점은 $k$, 정점 $k$로부터 정점 $i$까지의 최단 거리를 $d_i$라고 한다. 2. 정점 $x$에서 정점 $y$로 가는 가중치 $z$인 간선이 존재할 때 $w(x, y) = z$라고 한다. 3. $d_k$는 $0$, 나머지 $d_i$는 모두 $\infty$로 초기화한다. 4. 빈 덱에 정점 $k$를 추가한다. 5. 덱의 맨 앞에서 정점 하나를 뺀다. 이 정점을 $u$라고 하자. 6. $u$가 아직 선택되지 않았으면, $u$를 선택하고 $u$와 인접한 정점을 확인.. 110. Breadth First Search 너비 우선 탐색(Breadth First Search, BFS)은 노드를 탐색하고, 그 노드와 인접한 노드를 탐색하고, 그 노드들과 인접한 노드를 탐색하는 식으로 탐색을 시작한 노드에서 가까운 노드부터 차례로 탐색을 진행하는 탐색 방법이다. 이전에 탐색한 노드들과 인접해서 이후에 탐색할 예정이지만 아직 탐색하지 않은 노드들을 저장하기 위해 보통 큐가 사용된다. 탐색 과정에서 시작 노드에서 각각의 노드까지의 최단 경로의 길이를 알 수 있게 된다. DFS와 마찬가지로 인접한 노드가 여러 개 있을 경우 문제 상황에 맞게 탐색 순서를 정하면 된다. DFS를 설명한 글에 나온 그래프의 노드 $\text{D}$에서 BFS를 시작하면 BFS는 다음과 같이 진행된다.먼저 노드 $\text{D}$를 방문한다. 노드 $\.. 이전 1 다음
