• DFS vs BFS 한 눈에 이해하기

• DFS vs BFS 한 눈에 이해하기

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

• 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법
• 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는
  순회 방법이다.
• 깊게(deep) 탐색하기 전에 넓게(wide) 탐색하는 것이다.
• 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택한다.
• 너비 우선 탐색(BFS)이 깊이 우선 탐색(DFS)보다 좀 더 복잡하다.

너비 우선 탐색(BFS)의 특징

• 직관적이지 않은 면이 있다.
• BFS는 시작 노드에서 시작해서 거리에 따라 단계별로 탐색한다고 볼 수 있다.
• BFS는 재귀적으로 동작하지 않는다.
• 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사 해야 한다. → 검사하지 않을 경우 무한루프에 빠질 위험이 있다.
  
• BFS는 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료 구조인 큐(Queue)를 사용한다.
• 선입선출(FIFO) 원칙으로 탐색한다.
• 일반적으로 큐를 이용해서 반복적 형태로 구현하는 것이 가장 잘 동작한다.

너비 우선 탐색(BFS)의 과정

• 깊이가 1인 모든 노드를 방문하고 나서 그 다음에는 깊이가 2인 모든 노드를,
  그 다음에는 깊이가 3인 모든 노드를 방문하는 식으로 계속 방문하다가 더 이상 방문할 곳이
  없으면 탐색을 마친다.

DFS와 BFS 차이 그림으로 보기

예시로 이해하기

• 8에서 시작한다.
• 8에서 3과 10으로 이동한다.
• 3은 1과 6으로, 10은 14로 이동한다.
• 6은 4와 7로 이동한다. 14는 13으로 이동한다

코드로 이해하기

int n = 14;
        List<Integer>[] node = new List[n + 1];

        for (int i = 0; i <= n; i++) {
            node[i] = new ArrayList<Integer>();
        }

				node[8].add(3);
        node[8].add(10);
        node[3].add(1);
        node[3].add(6);
        node[10].add(14);
        node[6].add(4);
        node[6].add(7);
        node[14].add(13);

				boolean[] searchCheck = new boolean[n + 1];
        Stack<Integer> searchQueue = new Stack<>();

				searchQueue.add(8);

			  while (!searchQueue.isEmpty()) {
            int curPoint = searchQueue.pop(); 

						searchCheck[curPoint] = true;

						for (Integer nextPoint : node[curPoint]) {
                if (!searchCheck[nextPoint]) { 
                    searchQueue.add(nextPoint)
                }
            }
        }