엣지를 따라 모든 노드를 방문하는 것을 그래프 탐색이라고 한다.
대표적으로 DFS(깊이 우선 탐색), BFS(너비 우선 탐색)이 있다.
Depth First Search (깊이 우선 탐색)
깊이 우선 탐색은 기본적으로 Stack이다. (Last In First Out)
오른쪽 왼쪽 상관은 없음
예제
graph_list = [
[], # 0번 도시(없음)
[2, 3, 8], # 1번 도시
[1, 7], # 2번 도시
[1, 4, 5], # 3번 도시
[3, 5], # 4번 도시
[3, 4], # 5번 도시
[7], # 6번 도시
[2, 6, 8], # 7번 도시
[1, 7] # 8번 도시
]|
1번 도시 방문
|
Done = [1]
Done = [1, 2] Done = [1, 2, 7] Done = [1, 2, 7, 6] Done = [1, 2, 7, 6, 8] Done = [1, 2, 7, 6, 8, 3] Done = [1, 2, 7, 6, 8, 3, 4] Done = [1, 2, 7, 6, 8, 3, 4, 5] |
예제 문제 DFS 코드(함수)로 구현하기
graph = [
[], #0
[2, 3, 8], #1
[1, 7], #2
[1, 4, 5], #3
[3, 5], #4
[3, 4], #5
[7], #6
[2, 6, 8], #7
[1, 7], #8
]
def dfs(graph, start_city) :
to_visit = graph[start_city]
done_visit = [start_city]
while to_visit:
visited = to_visit.pop()
if visited not in done_visit:
done_visit.append(visited)
to_visit.extend(graph[visited])
return done_visit
dfs(graph, 1)
>>> [1, 8, 7, 6, 2, 3, 5, 4]pop으로 꺼내서 할당하는 visited의 값이 가장 큰 숫자부터 고르기때문에 [1, 8, 7, 6, 2, 3, 5, 4]가 나온다. 예제 문제처럼 pop으로 꺼내는 도시가 가장 작은 숫자부터 고르게 하려면 어떻게 해야 할까?
def dfs_2(graph, start_city) :
to_visit = list(reversed(graph[start_city])) #💛
done_visit = [start_city]
while to_visit:
visited = to_visit.pop()
if visited not in done_visit:
done_visit.append(visited)
temp = graph[visited] #💛
temp_reversed = list(reversed(temp)) #💛
to_visit.extend(temp_reversed) #💛
return done_visit
dfs_2(graph, 2)
>>> [1, 2, 7, 6, 8, 3, 4, 5]뒤집어서 맨 뒤부터 추가해주기!
BFS의 경우 pop()을 pop(0)으로 변경해주면 끝인데,
속도 이슈가 있기때문에 코딩테스트에 권장하지 않음
-> 너비 우선 탐색법이 필요한 경우 depop을 고려
'Code > algorithm' 카테고리의 다른 글
| 알고리즘 | BFS 활용하여 특정 도시 거리 계산 문제 풀기 (0) | 2024.04.01 |
|---|---|
| 알고리즘 | queue(FIFO) 속도이슈를 해결할 수 있는 deque (0) | 2024.04.01 |
| 알고리즘 | 정렬 (선택정렬/삽입정렬/버블정렬) (0) | 2024.04.01 |
| 알고리즘 | 탐색 기본 - Stack, Queue (0) | 2024.04.01 |
| 알고리즘 | 탐색 기본, 인접행렬과 인접리스트 (0) | 2024.04.01 |