섬나라 아일랜드

문제

제한 사항

입출력 예

풀이

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;
    for (let k = 0; k < dx.length; k++) {
      let nx = x + dx[k];
      let ny = y + dy[k];
      if (nx >= 0 && ny >= 0 && nx < n && ny < n && board[nx][ny]) {
        DFS(nx, ny);
      }
    }
  }

  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      if (board[i][j] === 1) {
        // 섬의 시작 점을 찾고
        DFS(i, j); // 그 섬과 연결된 모든 땅을 바다로 만들고 돌아옴
        answer++; // 그리고 숫자를 세어줌, DFS의 호출횟수가 즉 섬의 개수
      }
    }
  }

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

• 호출되는 횟수가 섬의 수임을 이해하자.

function solution2(board) {
  let answer = 0;
  let n = board.length;

  function bfs(i, j) {
    let dx = [-1, -1, 0, 1, 1, 1, 0, -1];
    let dy = [0, 1, 1, 1, 0, -1, -1, -1];
    let queue = [];
    queue.push([i, j]);
    while (queue.length) {
      let [x, y] = queue.shift();
      for (let i = 0; i < dx.length; i++) {
        let nx = x + dx[i];
        let ny = y + dy[i];
        if (nx >= 0 && ny >= 0 && nx < n && ny < n && board[nx][ny]) {
          board[nx][ny] = 0;
          queue.push([nx, ny]);
        }
      }
    }
  }

  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      if (board[i][j] === 1) {
        // 섬의 입구찾기
        board[i][j] = 0; // bfs 시작, 그전에 0으로 바꿔주고 시작하기
        answer++;
        bfs(i, j);
      }
    }
  }

  return answer;
}

let arr2 = [
  [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(solution2(arr2));

• bfs를 이용한 방식.