반응형
1. BFS(Breadth First Search; 너비 우선 탐색)의 개념
■ 그래프에서 모든 노드를 한번씩 탐색하기 위한 방법
■ 루트 노드[또는 임의의 노드]에서 시작하여, 형제(sibling) 노드를 탐색한 후, 각 레벨에 있는 노드를 차례대로 탐색하는 방법.
■ Queue를 이용하여 구현
2. BFS 노드 방문 순서
■ 결과 : 1 → 2 → 3 → 4 → 7 → 8 → 9 → 5 → 6 → 10
- step1) 루트 노드에서 시작하여, 같은 레벨에 있는 모든 노드를 탐색하고 큐에 추가한다.
- step2) 큐에서 하나씩 노드를 꺼내면서 그 노드와 연결된 인접 노드를 탐색하고, 탐색된 노드는 큐에 추가한다.
- step3) 큐가 빌 때까지 step1과 step2를 반복하며 모든 노드를 탐색한다.
3. 그래프 표현
■ "그래프"는 "인접 리스트"로 표현하여 보다 이해하기 쉬운 형태로 만들 수 있다.
| 1 | 2, 3 |
| 2 | 1, 4 |
| 3 | 1, 7, 8, 9 |
| 4 | 2, 5, 6 |
| 5 | 4 |
| 6 | 4 |
| 7 | 3, 10 |
| 8 | 3 |
| 9 | 3 |
| 10 |
■ "인접 리스트"는 "2차원 배열[리스트]" 또는 "테이블[dictionary]" 자료구조로 코드화 한다.
|
1
2
3
4
5
6
7
8
9
10
11
12
|
let graph = []
graph['0'] = [] // index 0: 사용하지 않음.
graph['1'] = ['2', '3']
graph['2'] = ['1', '4']
graph['3'] = ['1', '7', '8', '9']
graph['4'] = ['2', '5', '6']
graph['5'] = ['4']
graph['6'] = ['4']
graph['7'] = ['3', '10']
graph['8'] = ['3']
graph['9'] = ['3']
graph['10'] = ['7']
|
cs |
4. JavaScript 코딩
- JavaScript로 구현한 Queue 참고: https://languagestory.tistory.com/400
큐(Queue) 구현 및 테스트 (JavaScript, Python)
1. Queue 개념■ 선입선출 (FIFO): 큐에서 데이터는 먼저 들어온 순서대로 출력된다.■ enqueue: 큐에 데이터를 삽입하는 작업■ dequeue: 큐에서 데이터를 제거하는 작업■ Front: 큐의 앞쪽 (데이터가
languagestory.tistory.com
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
|
// 'queue.js' 파일에서 Queue 클래스를 가져옴
const Queue = require('./queue.js');
// BFS 알고리즘 구현
const bfs = (graph, currNode, visited) => {
// Queue 인스턴스를 생성하여 사용
const queue = new Queue();
// 시작 노드를 큐에 추가하고 방문처리
queue.enqueue(currNode);
visited[currNode] = true;
// 큐가 비어있지 않으면 계속해서 탐색
while (queue.getLength() > 0) { // 큐가 빌 때까지 반복
const nextNode = queue.dequeue(); // 큐에서 하나의 노드를 꺼냄 (이 노드를 탐색)
console.log(nextNode); // 현재 노드를 출력 (탐색한 노드)
// 꺼낸 노드의 인접 노드들을 탐색
for (const neighborNode of graph[nextNode]) {
// 방문하지 않은 인접 노드가 있으면 큐에 추가하고 방문처리
if (!visited[neighborNode]) {
queue.enqueue(neighborNode); // 큐에 인접 노드를 추가
visited[neighborNode] = true; // 해당 노드를 방문했다고 표시
}
}
}
}
// 그래프의 연결 정보 (인접 리스트 형태로 표현)
const graph = [
[], // 0번 노드: 사용하지 않음
[2, 3, 4], // 1번 노드: 2, 3, 4번 노드와 연결
[1], // 2번 노드: 1번 노드와 연결
[1, 5, 6], // 3번 노드: 1, 5, 6번 노드와 연결
[1, 7], // 4번 노드: 1, 7번 노드와 연결
[3, 8], // 5번 노드: 3, 8번 노드와 연결
[3], // 6번 노드: 3번 노드와 연결
[4], // 7번 노드: 4번 노드와 연결
[5] // 8번 노드: 5번 노드와 연결
]
// 방문 여부를 체크하는 배열 (그래프 크기만큼 false로 초기화)
const visited = Array(graph.length).fill(false);
// 1번 노드부터 BFS 탐색 시작
bfs(graph, 1, visited); // 1번 노드부터 BFS 탐색
|
cs |
반응형
'알고리즘(코딩테스트)' 카테고리의 다른 글
| [DFS] 조합(combination) (0) | 2025.02.16 |
|---|---|
| 큐(Queue) 구현 및 테스트 (JavaScript, Python) (0) | 2025.02.16 |
| [DFS] 순열(permutation) (0) | 2025.02.16 |
| [백준][DFS][난이도:하] 단지번호 붙이기 (2667번) (0) | 2025.02.16 |
| [백준][DFS][난이도:하] 차이를 최대로 (10819번) (0) | 2025.02.16 |