BFS, DFS

BFS와 DFS 개념

---

BFS (Breadth-First Search) : 너비우선 탐색

트리탐색의 Level-order와 동일한 기법으로 탐색.

DFS (Depth-First Search) : 깊이우선 탐색

트리탐색의 Inorder와 동일한 기법으로 탐색.

BFS와 DFS의 기본 코드 형태 (틀)

---

< BFS (Breadth-First Search) : Queue 활용 >

Queue가 Empty일 때까지 loop를 돌려 모든 경우를 탐색한다.

public void BFS(/* input */){
    Queue <Integer> q = new LinkedList <Integer>();
    
    q.offer(/* input */);
 
    while(!q.isEmpty()){
        currentVertex = q.poll();
        // 다음 정점에 방문하지 않았다면
        // 다음 정점을 offer
        // 현재 정점 visited = true
 
        // 모든 탐색을 마칠 때까지 q.isEmpty == false
    }
}

< DFS (Depth-First Search) : Recursive 활용 >

Recursive를 이용해 모든 경우를 탐색한다.

public void DFS(/* input */){
    // n은 input으로 들어옴
    visit[n] = true;
 
       for(/* loop 조건 */){
        
        if(/* 다음 정점에 방문하지 않았고, 이동할 수 있다면 */){
            DFS(/* input */);
        }
    }
}

위에서 BFS - Queue, DFS - Recursive로 구현했는데,

원래 BFS는 Queue, DFS는 Stack이라고들 한다.

위 DFS코드의 재귀함수는 Stack처럼 동작하기 때문에 결국 같은 말이다.

기본 틀이 되는 코드는 위에서 확인했다.

그럼 이 개념을 실전 알고리즘에 어떻게 적용할 수 있을까?

또, 어떤 형태로 나타날까?

알고리즘에서의 BFS와 DFS (실전)

---

보통 알고리즘에서 BFS, DFS는 2차원 배열이 주어지고, 배열을 완전탐색 하는 형태로 나타난다.

이 때, 아래와 같은 탐색을 진행하며 BFS, DFS를 적용한다.

(0, 0)부터 시작해 상, 하, 좌, 우 중 어느 방향으로 이동할 수 있는지 검사해 가능한 위치로 탐색한다.

자세한 탐색 방법은 아래 글에 있다.

2018/10/13 - [Developer/Memo] - [알고리즘 Tip] 2차원 배열 상하좌우 이동

보통 위와 같은 문제의 출력값은 '최단 탐색'이나 '가장 많/적은 횟수' 등이기 때문에

탐색 결과값을 또다른 2차원 배열에 일일이 기록하면서 탐색하면 자동으로 값을 찾을 수 있게 된다.