깊이 우선 탐색 DFS(Depth First Search)
- 하나의 루트에서 탐색하다가 특정 상황에서 깊게 들어가서 확인하고 다시 돌아와서 다른 루트로 탐색하는 방법
- 백트래킹에서 사용
- 재귀, 스택으로 구현
구현 과정
- 탐색 시작 노드를 스택에 넣고 방문 처리
- 스택에서 원소를 꺼내서 방문하지 않은 인접 노드가 있을 경우 그 노드를 스택에 넣고 방문 처리
- 스택이 빌때까지 반복
DFS 문제 - 2468번 안전 영역
https://www.acmicpc.net/problem/2468
2468번: 안전 영역
재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는
www.acmicpc.net
DFS 문제 - 10026번 적록색약
https://www.acmicpc.net/problem/10026
10026번: 적록색약
적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록)
www.acmicpc.net
DFS 문제 - 1987번 알파벳
https://www.acmicpc.net/problem/1987
1987번: 알파벳
세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으
www.acmicpc.net
'CS > 자료구조&알고리즘' 카테고리의 다른 글
| [알고리즘] 플로이드 와샬(Floyd Warshall) - 모든 정점의 최소 비용 (0) | 2022.09.19 |
|---|---|
| [알고리즘] 위상 정렬(Topological Sort) - 줄 세우기, 선수 과목 (3) | 2022.09.19 |
| [알고리즘] 너비 우선 탐색 BFS(Breadth First Search) - 최단 경로 (0) | 2022.09.18 |
| [알고리즘] 동적 계획법(Dynamic Programming) (0) | 2022.09.17 |
| [알고리즘] 자료구조 - 스택, 큐, 덱, 힙, 우선순위 큐 (0) | 2022.09.16 |