BFS(너비우선탐색) vs DFS(깊이우선탐색)

 

알고리즘 문제를 풀기 위해서 간단하게 BFS와 DFS에 대해서 정리하고자 합니다. 

 

안녕하세요, 독자 여러분은

중간고사 공부를 할때는 어떤방식으로 공부를 하시나요? 

 

1. BFS (Breadth-First Search, 너비 우선 탐색)

"여러개의 과목을 조금씩 나누어서 정복한다"

- 일단 자기 위치에서 '상하좌우' 1칸씩만 가봅니다. 그 다음, 그 1칸 떨어진 곳들에서 또 1칸씩(시작점에서 2칸)을 가봅니다. (범위를 넓혀가면서 넓게 탐색하는 방식)

- 최단거리를 구할때 주로 사용

 

1) 필수 구성요소

    (1) 큐 (Queue): "선입선출(FIFO)" 대기열

        - "다음에 방문할 곳"들을 저장하기 위한 대기줄

        - 가까운 곳(레벨 1)을 먼저 큐에 다 넣었기 때문에, 큐에서 순서대로 꺼내면 가까운 곳부터 처리할 수 밖에 없습니다. 

    (2) visited (방문 배열): "방문 기록"

       - "이미 가본 곳"을 체크합니다

       - 이게 없으면 두 노드 사이를 무한정 왔다 갔다 하는 무한루프에 빠집니다. 

2) 알고리즘

     (1) Queue와 visited(방문배열)을 선언한다

     (2) 시작점을 Queue에 넣는다.

     (3) 시작점의 visited를 true로 표시한다

     (4)  Queue가 빌 때까지 다음을 반복한다

           a) Queue에서 현재 위치(A)를 꺼낸다.  
           b) (A)에서 상하좌우로 다음 위치(B)를 탐색한다.

           c) 다음 위치(B)가 (배열 범위를 벗어났거나, visited가 true이거나, 벽(0)이거나) 하면 무시한다. (Continue)

           d) (위 3가지 체크를 통과했다면)
                  - 다음 위치(B)의 visited를 true로 표시한다.
                  - 다음 위치(B)를 Queue에 넣는다.

 

 

3) 어떤 문제를 BFS로 풀어야 할까? 

- 한마디로 "최단 거리" 또는 "최소 횟수"를 묻는 문제는 BFS로 푼다고 생각하면 90% 이상 맞습니다

 

   (1) 최단 거리/ 최소 횟수 문제(가장 기본)

       - 미로 탐색 (백준 2178) : 

   (2) 특정 상태를 만드는 최소 연산 문제

       - A를 B로 바꾸기 (백준 1697번 숨바꼭질)

       - 퍼즐 맞추기

    (3) 연결된 영역(컴포넌트) 동시 탐색

       - 토마토 (백준 7576번)

•  

4) 시간 복잡도

   (1) 인접리스트 (그래프 저장 방식) : O(V + E)

       - V : 정점의 수, E : 간선의 수

       - 모든 정점(V)을 한번씩 큐에 넣고, 모든 간선(E)를 한번씩 검사 함

   (2) 인접 행렬 (N x M 미로) : O(V^2)

 

2. DFS (Depth-First Search, 깊이 우선 탐색)

"과목 1개씩 끝을 내고 다음 과목으로 넘어간다"

- 일단 '오른쪽'으로 갈 수 있을 때까지 한 방향으로 끝까지 가봅니다. (깊게, 한우물 파기)

 

1) 필수 구성요소

 

2) 알고리즘

 

3) 어떤 문제를 BFS로 풀어야 할까? 

 

4) 시간 복잡도

 

 

참고자료)

https://www.youtube.com/watch?v=BsYbdUnKZ-Y