알고리즘
너비 우선 탐색(BFS, Breadth First Search)
minjaem
2023. 10. 29. 12:04
너비 우선 탐색?
어떤 노드를 방문하여 확인한 후, 목표한 노드가 아니면 그 노드와 연결된 정점들 중에서 우선 순위가 동일한 다른 노드를 찾고 그 순위에 없으면 그 다음 순위 노드를 차례대로 찾는 방법
즉, 깊게 탐색하기 전 넓게 탐색하는 방법이다.
* 두 노드의 최단 경로를 찾고 싶은 경우에 이 방법을 선택
* BFS보다 복잡하다.
구현 방법
큐(Queue)를 사용한다.
문제
다음과 같이 입력이 주어질 때 너비 우선 탐색을 한 순서대로 노드의 인덱스를 공백 구분으로 출력하시오.
데이터
graph = {'E': ['D', 'A'],
'F': ['D'],
'A': ['E', 'C', 'B'],
'B': ['A'],
'C': ['A'],
'D': ['E','F']}
출력
E D A F C B문제 풀이
가까운 정점을 먼저 방문하고, 먼 정점은 나중에 방문하게 되며 다음과 같이 거리와 노드를 나눌 수 있다.
자, 이제 아래와 같이 큐를 통해서 탐색을 시작한다.
E가 먼저 큐에 쌓이게 되고, 실행되며 Current로 이동한다.
이 때, D와 A가 큐에 쌓이게 된다.
(E는 방문경로로 이동)
큐는 FIFO(First In First Out) 방식으로, D가 실행되며 Current로 이동한다.
이 때, 큐에는 F가 쌓이게 된다.
(D는 방문경로로 이동한다.)
스택과 다르게, 큐에서는 먼저 쌓인 A가 실행되며 Current로 이동한다.
이 때, C와 B가(A 이후에 실행되는 경로 노드) 큐에 쌓이게 된다.
(A는 방문경로로 이동한다.)
이러한 방식으로 너비 우선 탐색을 실행하게 되며 결과적으로는 다음과 같은 방문경로가 나온다.
코드 풀이
function dfs(graph, start) {
let visited = []
let stack = [start]
// stack의 값이 다 빠져나갈 때 종료
while (stack.length !== 0) {
let n = stack.shift()
// 방문했던 상위 노드 제외 로직
if (!visited.includes(n)) {
visited.push(n)
let sub = graph[n].filter(x => !visited.includes(x))
for (let i of sub) {
stack.push(i)
}
}
}
return visited;
}
console.log(dfs(graph, 'E'))
[참고]
인프런, 제주코딩베이스캠프 Code Festival: JavaScript 100제: 모든 이미지와 풀이는 해당 강의 자료를 참고했습니다.