[Algorithm] DFS (다차원 배열)

https://blog.encrypted.gg/942

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

대부분의 내용을 위의 게시물을 참고해 작성한 글이다.

---

DFS의 기본 개념

이전 게시물에서 BFS에 대해 알고 있다는 것을 전제로 설명한다. DFS를 사용하면 다차원 배열에서 각 칸을 깊이를 우선으로 방문할 수 있다. 그리고 DFS는 재귀로도 자주 사용되는데, 여기에서는 스택을 사용한 DFS만 설명하겠다.

 

DFS에는 스택이 사용된다. BFS와 유일하게 다른 점은 큐 대신 스택이 사용된다는 것 밖에 없다. 동작 순서를 정리하면 다음과 같다.

1. 시작점을 스택에 집어넣은 후 방문 처리를 한다. (여기까지가 초기 세팅)
2. 스택의 앞에서 값을 꺼낸 후, 그 칸에 인접한 칸들을 검사한다. (여기에서는 상하좌우 네 칸만 생각)
3. 이미 방문한 칸이면 무시하고, 방문하지 않았다면 방문 처리를 한 후 스택에 저장한다.
4. 스택이 빌 때까지 2~3 과정을 반복한다.

모든 칸이 스택에 한 번씩 들어갔다 나오므로 N개의 칸이 있다고 한다면 DFS를 한 번 실행할 때의 시간 복잡도는 O(N)이다.

 

이렇게 하면 시작점과 연결된 모든 칸들을 방문할 수 있다. (Flood Fill)

DFS로 Flood Fill 알고리즘을 실행하는 모습 (출처: 위키피디아 플러드 필)

 

BFS와 DFS

BFS와 DFS는 비슷해보이지만 차이점이 있다.

• 2차원 배열에서의 방문 순서

먼저 DFS의 방문 순서를 보자. 아래 사진을 보면 DFS는 한 방향으로 막힐 때까지 쭉 직진하는 것을 알 수 있다.

https://www.linkedin.com/pulse/dfs-bfs-coding-interview-3-steps-success-jimmy-zhang-hldgf/

BFS는 시작점으로부터 떨어진 거리순으로 방문하는 것을 알 수 있다. 

https://www.linkedin.com/pulse/dfs-bfs-coding-interview-3-steps-success-jimmy-zhang-hldgf/

• 거리 측정

이전 게시물에서는 BFS를 사용해 다차원 배열에서 시작점부터 각 칸까지의 거리를 계산하는 활용을 배웠다. 하지만 이 활용은 거리순으로 방문하는 BFS에만 적용되므로 DFS로는 거리 측정을 할 수 없는 것을 꼭 알고 있어야 한다.

마무리

다차원 배열에서의 DFS는 분량이 적다. 사실 DFS는 다차원 배열보다 그래프나 트리 방문에서 필요하기 때문이다. 여기에서는 DFS는 스택을 써서 다차원 배열의 순회를 처리할 수 있다~ 정도로만 알고 가자.