[JavaScript/section 9] 07 - 섬나라 아일랜드(BFS)

📌 07 - 섬나라 아일랜드(BFS 활용)

N*N의 섬나라 아일랜드의 지도가 격자판의 정보로 주어진다. 각 섬은 1로 표시되어 상하좌우와 대각선으로 연결되어 있으며, 0은 바다이다. 섬나라 아일랜드에 몇 개의 섬이 있는지 구하는 문제이다.

만약 위와 같다면 섬의 개수는 총 5개이다.

 

섬나라 아일랜드(DFS) 문제와 같지만 이번에는 BFS 알고리즘을 이용해 풀어보았다. 영역을 탐색하는 문제의 경우에는 본인에게 편한 방법을 이용하여 풀면 될 것 같다..🤔

 

📝 풀이 방법

• 이중 for 문을 돌면서 1이 나온다면 섬을 발견한 것이므로 배열에서 해당 좌표를 0으로 재할당하고 answer++을 한다. 또한, 넓이 우선 탐색을 위해 큐에 해당 좌표를 추가한다.
  
• while 문을 돌면서 큐에서 shift 한 좌표에 대해 상하좌우와 대각선을 탐색하여 연결된 좌표가 있다면 모두 0으로 재할당하고 큐에 추가한다.
• 위와 같은 과정을 반복하다가 큐에 아무것도 존재하지 않아 while 문을 빠져나온다면 하나의 섬을 모두 탐색한 것이므로 다른 섬을 찾는다.

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) {
        // 먼저 0으로 체크한 후 큐에 추가
        board[i][j] = 0;
        queue.push([i, j]);
        answer++;

        // 하나의 섬을 발견하여 주변을 탐색하는 과정
        while (queue.length) {
          let [x, y] = queue.shift();

          for (let i = 0; i < 8; i++) {
            let nx = x + dx[i];
            let ny = y + dy[i];

            // 경계선 확인 필수 ❗
            if (nx < 0 || ny < 0 || nx >= n || ny >= n || board[nx][ny] === 0)
              continue;

            board[nx][ny] = 0;
            queue.push([nx, ny]);
          }
        }
      }
    }
  }

  return answer;
}

let arr = [
  [1, 1, 0, 0, 0, 1, 0],
  [0, 1, 1, 0, 1, 1, 0],
  [0, 1, 0, 0, 0, 0, 0],
  [0, 0, 0, 1, 0, 1, 1],
  [1, 1, 0, 1, 1, 0, 0],
  [1, 0, 0, 0, 1, 0, 0],
  [1, 0, 1, 0, 1, 0, 0],
];

console.log(solution(arr));