섬나라 아일랜드(DFS) - Node.js

프동프동·2022년 8월 10일
0

알고리즘 - Node.js

목록 보기
105/116
post-thumbnail

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


문제

N*N의 섬나라 아일랜드의 지도가 격자판의 정보로 주어집니다. 각 섬은 1로 표시되어 상하좌 우와 대각선으로 연결되어 있으며, 0은 바다입니다. 섬나라 아일랜드에 몇 개의 섬이 있는지 구하는 프로그램을 작성하세요.

만약 위와 같다면

입력

첫 번째 줄에 자연수 N(3<=N<=20)이 주어집니다. 두 번째 줄부터 격자판 정보가 주어진다.

출력

첫 번째 줄에 섬의 개수를 출력한다.

입력 예시 1

1100010

0110110

0100000

0001011

1101100

1000100

1010100

출력 예시 1

5


해결방법

function solution(board) {
  let answer = 0;
  let board_length = 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 < 8; k++) {
      let nx = x + dx[k];
      let ny = y + dy[k];
      if (
        nx >= 0 &&
        nx < board_length &&
        ny >= 0 &&
        ny < board_length &&
        board[nx][ny] === 1
      ) {
        DFS(nx, ny);
      }
    }
  }
  for (let i = 0; i < board_length; i++) {
    for (let j = 0; j < board_length; j++) {
      if (board[i][j] === 1) {
        answer++;
        DFS(i, j);
      }
    }
  }
  return answer;
}

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

profile
좋은 개발자가 되고싶은

0개의 댓글