1. DFS(Depth First Search; 깊이 우선 탐색)의 개념
■ 루트 노드[또는 임의의 노드]에서 시작하여 형제 (sibling) 노드로 넘어가기 전에 시작한 분기의 마지막 노드까지 깊게 탐색하는 방법
■ 그래프에서 모든 노드를 한번씩 탐색하기 위한 방법
■ 스택 또는 재귀함수를 이용하여 구현
2. 그래프 탐색 순서
■ 루트 노드에서 시작하여 DFS 결과 : 1 → 2 → 4 → 5 → 6 → 3 → 7 → 10 → 8 → 9
3. 그래프 표현
■ Graph는 배열[리스트] 또는 테이블[dictionary]로 표현한다.
4. 파이썬 코딩
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
|
def dfs(graph, start, visited = []):
visited.append(start)
for node in graph[start]:
if node not in visited:
dfs(graph, node, visited)
return visited
if __name__ == '__main__':
graph = dict()
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']
result = dfs(graph, '1')
print(result)
|
cs |
5. JavaScript 코딩
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
|
function dfs(graph, v, visited = []) {
visited[v] = true;
console.log(v);
for (let node of graph[v]) {
if (!visited[node]) {
dfs(graph, node, visited);
}
}
}
graph = []
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']
result = dfs(graph, '1')
console.log(result)
|
cs |
'알고리즘(코딩테스트)' 카테고리의 다른 글
[백준] 주유소 (0) | 2024.10.05 |
---|---|
[백준] 수들의 합 (0) | 2024.10.05 |
[백준] 설탕 배달 (0) | 2024.10.04 |
[백준] 읽어버린 괄호 (0) | 2024.10.04 |
[백준] ATM (1) | 2024.10.03 |