[알고리즘] 3. DFS

Wonder_Land🛕·2022년 12월 15일
0

[알고리즘]

목록 보기
3/11
post-thumbnail

[Reference] : 위 글은 다음 내용을 제가 공부한 후, 인용∙참고∙정리하여 만들어진 게시글입니다.


  1. DFS
  2. Q&A
  3. 마치며

1. BFS

  • DFS(Depth First Search)
    : 다차원 배열에서 각 칸을 방문할 때, 깊이를 우선으로 방문하는 알고리즘

1) 다차원 배열의 DFS의 방법

  1. 시작하는 칸을 큐에 넣고, 방문했다는 표시를 남김

  2. 스택에서 원소를 꺼내어, 그 칸의 상하좌우로 인접한 칸에 대해 3번을 진행

  3. 해당 칸을 이전에 방문했다면 아무것도 하지 않고, 처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 스택에 삽입

  4. 스택가 빌 때까지 2번을 반복

DS의 시간복잡도는,
방문했다는 표시를 남기기 때문에 모든 칸은 스택에 1번씩만 들어가게 됨.
따라서 시간 복잡도는, 칸이 N개 일 때 O(N).
만약 행이 R개, 열이 C개라면 O(RC).

BFS에서 큐가 스택으로 변한 것 외에는 전부 똑같음.
즉, 큐를 쓰면 BFS, 스택을 쓰면 DFS.


2) 다차원 배열의 BFS의 구현

BFS와 동일하고, 큐가 스택으로만 바뀌면 됨.

(코드가 커서 '바킹독님의 깃헙 링크'를 참고)


3) BFS vs DFS

BFS와 DFS는, 큐와 스택을 쓴다는 차이점이 있지만, 원소 하나를 빼내고 주변을 살펴본다는 알고리즘의 흐름은 동일.

하지만 방문순서에서 가장 큰 차이가 있음.

BFS는 시작점을 중심으로, 동심원처럼 퍼져나감.
(BFS의 성질, 거리 순으로 원소를 방문함)
DFS는 한 방향으로 막힐 때까지 나아감.

따라서, BFS에서 사용한, "현재 칸으로부터 인접한 칸은 (현재 칸 + 1)이다"는 DFS에서는 성립하지 않음.

결국, 우리는 다차원 배열에서 DFS를 굳이 써야 하는 이유가 없음.
Flodd Fill은 어느 것을 써도 되지만, 거리 측정은 BFS만 가능하므로 BFS가 더 용이.

대부분 다차원 배열을 순회하는 문제는 BFS를 사용할 것.
(DFS는 그래프에서 더 다룰 것)


3. Q&A

-


4. 마치며

-

[Reference] : 위 글은 다음 내용을 제가 공부한 후, 인용∙참고∙정리하여 만들어진 게시글입니다.

profile
아무것도 모르는 컴공 학생의 Wonder_Land

0개의 댓글