[실전 알고리즘] 0x0A강 - DFS

1. 알고리즘 설명 DFS - 다차원 배열에서 각 칸을 방문할 때 깊이를 우선으로 방문하는 알고리즘 2. 예시 1. 시작하는 칸을 스택에 넣고 방문했다는 표시를 남김 2. 스택에서 원소를 꺼내어 그 칸에 상하좌우로 인접한 칸에 대해 3번을 진행 3. 해당 칸을 이전에 방문했다면 아무 것도 하지 않고, 처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 스택에 삽입 4. 스택가 빌 때 까지 2번을 반복 모든 칸이 스택에 1번씩 들어가므로 시간복잡도는 칸이 N개일 때 O(N). 사실상 BFS에서 큐가 스택으로 바뀐 것이다. 큐 - BFS 스택 - DFS DFS도 BFS처럼 Flood Fill이 필요할 때 사용할 수 있다. BFS와 DFS는 방문 결과는 똑같지만 방문 순서에서 큰 차이가 있다. DFS 구현..

2022.02.02