그래프 4) DFS와 BFS의 차이

그래프를 탐색하는 방법에는 DFS(Depth First Search: 깊이 우선 탐색)과 BFS(Breadth First Search: 넓이 우선 탐색) 두 가지가 있다.

 

DFS는 루트노드에서 시작해 다음 분기로 넘어가기 전 해당 분기를 완벽하게 탐색하는 방식을 말한다.

BFS는 루트노드에서 시작해 인접한 노드를 먼저 탐색하는 방식으로 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다.

 

모든 노드를 방문하고자 하는 경우에는 DFS를 가까운 노드부터 탐색하기 위해서는 BFS를 사용한다.

검색 속도 자체는 BFS가 빠르지만 DFS가 더 간단하다.

검색 대상 그래프가 크거나 경로의 특징을 저장해둬야 하는 문제는 DFS를,

검색 대상의 규모가 크지 않고 최단거리를 구해야 하는 문제는 BFS가 유리하다.

 

DFS는 스택 또는 재귀함수로 구현하고 BFS는 큐를 이용해서 구현한다.

 

// DFS

function solution(board) {
  let answer = 0;
  let n = board.length;
  let dx = [-1, -1, 0, 1, 1, 1, 0, -1];
  let dy = [0, 1, 1, 1, 0, -1, -1, -1];

  function DFS(x, y) {
    board[x][y] = 0; // 0으로 바꿔준다
    for (let k = 0; k < 8; k++) { // 8방향 탐색
      let nx = x + dx[k];
      let ny = y + dy[k];
      if (nx >= 0 && nx < n && ny >= 0 && ny < n && board[nx][ny] === 1) { // 이동한곳이 섬일때
        console.log(nx, ny); // 섬일때 탐색
        DFS(nx, ny); // 섬일때 재귀탐색
      }
    }
  }

  // 2차원 배열 탐색
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      if (board[i][j] === 1) { // 1이면 섬
        answer++;
        console.log(i, j); // 시작점
        DFS(i, j);
        console.log("DFS end");
      }
    }
  }

  return answer;
}

// BFS

function solution(board) {
  let answer = 0;
  let n = board.length;
  let dx = [-1, -1, 0, 1, 1, 1, 0, -1];
  let dy = [0, 1, 1, 1, 0, -1, -1, -1];
  let queue = [];

  // 이차원 배열 탐색
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      if (board[i][j] === 1) { // 1이면 섬
        board[i][j] = 0; // 0으로 바꿔줌(back 방지)
        queue.push([i, j]); // 출발점
        answer++;
        while (queue.length) { // queue 배열이 비면 종료
          let [x, y] = queue.shift(); // x, y로 할당
          console.log(x, y);
          for (let k = 0; k < 8; k++) { // 8방향 탐색
            let nx = x + dx[k];
            let ny = y + dy[k];
            if (nx >= 0 && nx < n && ny >= 0 && ny < n && board[nx][ny] === 1) { // 섬일때
              board[nx][ny] = 0; // 0으로 바꿔줌
              queue.push([nx, ny]); // 섬도착 시 push해서 while문 돌려 다음 섬 탐색
            }
          }
        }
        console.log("BFS end");
      }
    }
  }

  return answer;
}