반응형
1. DFS(Depth First Search; 깊이 우선 탐색)의 개념
■ 그래프에서 모든 노드를 한번씩 탐색하기 위한 방법
■ 스택 또는 재귀함수를 이용하여 구현
■ 루트 노드[또는 임의의 노드]에서 시작하여 형제(sibling) 노드로 넘어가기 전에 시작한 분기의 마지막 노드까지 깊게 탐색하는 방법
2. DFS 노드 방문 순서
■ 결과 : 1 → 2 → 4 → 5 → 6 → 3 → 7 → 10 → 8 → 9
- 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 코딩
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
// 깊이우선탐색(DFS) 함수
const dfs = (graph, currNode, visited = []) => {
visited[currNode] = true; // 현재 노드 방문 처리
console.log(currNode); // 현재 노드 출력
// 현재 노드와 연결된 다른 노드들에 대해 탐색
for (let nextNode of graph[currNode]) {
if (!visited[nextNode]) { // 아직 방문하지 않은 노드에 대해서만 재귀 호출
dfs(graph, nextNode, visited); // 재귀 호출로 다음 노드 탐색
}
}
}
dfs(graph, '1') // 노드1 부터 깊이우선탐색(DFS) 시작
|
cs |
반응형
'알고리즘(코딩테스트)' 카테고리의 다른 글
| [백준][DFS][난이도:하] 노드사이의 거리 (1240번) (1) | 2025.02.16 |
|---|---|
| [백준][DFS][난이도:하] 유기농 배추 (1012번) (0) | 2025.02.16 |
| [백준] 주유소 (0) | 2024.10.05 |
| [백준] 수들의 합 (0) | 2024.10.05 |
| [백준] 설탕 배달 (0) | 2024.10.04 |