2022.12.24 - [백준 알고리즘] - [알고리즘] DFS & BFS 알고리즘(1) - 스택 자료구조와 큐 자료구조
[알고리즘] DFS & BFS 알고리즘(1) - 스택 자료구조와 큐 자료구조
본 알고리즘 포스팅의 주제인 DFS와 BFS 알고리즘에 대해 알기전에, 먼저 '그래프 탐색'이란 무엇인가에 대해서 알아보는 것이 필요하다. (본 알고리즘 포스팅은 유튜브 '이코테 2021 강의'를 참고
inho3213.tistory.com
지난 포스팅에서는
스택 자료구조와 큐 자료구조에 대한 내용을 정리했다.
이번 포스팅에서는 본격적으로 DFS 알고리즘에 대해 정리해보고자한다.
(본 알고리즘 포스팅은 유튜브 '이코테 2021 강의'를 참고하여 작성하였습니다.)
https://www.youtube.com/@dongbinna
동빈나
www.youtube.com
DFS 란?
DFS는 Depth-First Search 의 약자로
'깊이 우선 탐색'을 의미한다.
즉, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.
이런 DFS는 지난번 다룬 스택 자료구조를 띄고 있다.
DFS의 동작과정을 정리하면 다음과 같다.
1. 탐색 시작 노드를 스택에 삽입하고 방문 처리한다.
2. 스택 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있다면 그 노드를 스택에 넣고 방문처리한다.
만약 방문하지 않은 인접한 노드가 없다면 스택에서 최상단의 노드를 꺼낸다.
3. 2번의 과정을 더 수행할 수 없을때까지 반복한다.
위와 같은 설명을 글로만 읽으면 와닿지 않을 수 있기에
관련 이미지 자료를 가져와봤다. (물론 이것역시 이코테 강의에서....)
본 그래프에서 탐색 시작 노드는 명시된 방문 기준대로, '1'이 될것이다
따라서 시작 노드인 '1'을 스택에 넣고 위 그림처럼 방문 처리를 한다.
다음으로는 '1'에 방문하지 않은 인접노드 2, 3, 8 중에서
가장 작은 노드인 '2'를 스택에 넣고 방문 처리한다.
위와 같은 과정을 반복한다.
그러다보면, 위의 그림처럼
만약 방문하지 않은 인접한 노드가 없다면 스택에서 최상단의 노드를 꺼낸다.
에 해당하는 상황이 오게된다.
그렇다면 다시 최상단노드는 '7'이 되고,
7에 방문하지 않은 인접 노드 '8'을 스택에 넣고 방문 처리를 하게된다.
이러한 과정을 더이상 수행할 수 없을때까지 반복하게 되면
탐색순서는 이미지에 나타난 것처럼
1 - 2 - 7 - 6 - 8 - 3 - 4 - 5
가 된다.
다음 포스팅에서는....
BFS 알고리즘에 대해 다뤄보기 전에,
DFS 알고리즘을 적용해 해결이 가능한
알고리즘 문제를 풀어보는 것으로 하겠다
'백준 알고리즘 > Python' 카테고리의 다른 글
| [알고리즘] 그리디 알고리즘 - 백준 1541 파이썬 문제풀이: 잃어버린 괄호 (0) | 2023.01.05 |
|---|---|
| [알고리즘] 그리디 알고리즘 - 백준 11399 파이썬 문제풀이: ATM (4) | 2022.12.25 |
| [알고리즘] DFS & BFS 알고리즘(1) - 스택 자료구조와 큐 자료구조 (0) | 2022.12.24 |
| [알고리즘] 그리디 알고리즘 - 백준 1931 파이썬 문제풀이: 회의실 배정 (0) | 2022.12.24 |
| [알고리즘] 그리디 알고리즘 - 백준 11047 파이썬 문제풀이: 동전 0 (0) | 2022.12.23 |