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

📌 06 - 섬나라 아일랜드(DFS 활용)

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

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

 

📝 풀이 방법

미로 탐색 문제와 유사한 문제이므로 참고하면 좋을 듯하다. 

• 이중 for 문을 돌면서 1이 나온다면 섬을 발견한 것이므로 배열에서 해당 좌표를 0으로 재할당하고 answer++을 한다.
• 해당 좌표에 대해 DFS를 돌면서 상하좌우와 대각선으로 연결된 좌표가 있는지 탐색한다.
• 연결된 좌표가 있다면 0으로 재  할당하고 연결된 좌표로 이동한다.
• 더 이상 연결된 좌표가 없다면 DFS 함수를 모두 종료하고 이중 for 문을 돌면서 새로운 섬을 찾는다.

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];

  // 이중 for 문을 돌면서 섬을 찾는 중	
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      if (board[i][j] === 1) {
        board[i][j] = 0;
        answer++;
        DFS(i, j);
      }
    }
  }

  // DFS 돌면서 연결된 좌표를 탐색하는 중
  function DFS(x, y) {
    for (let k = 0; k < 8; k++) {
      let nx = x + dx[k];
      let ny = y + dy[k];

      if (nx >= 0 && ny >= 0 && nx < n && ny < n) {
        if (board[nx][ny] === 1) {
          board[nx][ny] = 0;
          DFS(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));