백준 4963 < 섬의 개수 > JavaScript

📍문제 링크

https://www.acmicpc.net/problem/4963

4963번: 섬의 개수

 

📍알고리즘 분류

- 그래프 이론

- 그래프 탐색

- 너비 우선 탐색

- 깊이 우선 탐색

 

📍문제 풀이

- 0과 1로 이루어진 좌표 평면이 주어질 때, 1은 땅이고  나머지(빈 공간과 0)는 바다이다

- 8 방면으로 연결되면 하나의 공간이라고 할 때, 섬의 갯수를 구하라

 

- 입력받는 방법이 조금 특이해서 shift로 하나씩 빼서 사용했다

- 1인 좌표에 대해 BFS를 실시하여 큐에 넣은 뒤 1을 0으로 바꿔주면 방문 체크를 따로 할 필요가 없다

 

📍코드 (JavaScript)

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const input = [];

const bfs = (r, c, map, height, width) => {
  const queue = [[r, c]];
  map[r][c] = 0;
  while (queue.length) {
    const [y, x] = queue.shift();
    // n, s, w, e
    // nw, ne, sw, se
    // n, ne
    if (y - 1 >= 0) {
      if (map[y - 1][x]) {
        queue.push([y - 1, x]);
        map[y - 1][x] = 0;
      }
      if (x + 1 < width && map[y - 1][x + 1]) {
        queue.push([y - 1, x + 1]);
        map[y - 1][x + 1] = 0;
      }
    }
    // s, sw
    if (y + 1 < height) {
      if (map[y + 1][x]) {
        queue.push([y + 1, x]);
        map[y + 1][x] = 0;
      }
      if (x - 1 >= 0 && map[y + 1][x - 1]) {
        queue.push([y + 1, x - 1]);
        map[y + 1][x - 1] = 0;
      }
    }
    // w, nw
    if (x - 1 >= 0) {
      if (map[y][x - 1]) {
        queue.push([y, x - 1]);
        map[y][x - 1] = 0;
      }
      if (y - 1 >= 0 && map[y - 1][x - 1]) {
        queue.push([y - 1, x - 1]);
        map[y - 1][x - 1] = 0;
      }
    }
    // e, se
    if (x + 1 < width) {
      if (map[y][x + 1]) {
        queue.push([y, x + 1]);
        map[y][x + 1] = 0;
      }
      if (y + 1 < height && map[y + 1][x + 1]) {
        queue.push([y + 1, x + 1]);
        map[y + 1][x + 1] = 0;
      }
    }
  }
};

rl.on("line", (line) => {
  input.push(line);
}).on("close", () => {
  const answer = [];
  while (input.length) {
    const [w, h] = input.shift().split(" ").map(Number);
    const board = [];
    for (let i = 0; i < h; i++) {
      board.push(input.shift().split(" ").map(Number));
    }

    // 1인 좌표에 대해 bfs 실행
    // 방문하면 0으로 바꾸기
    let count = 0;
    for (let i = 0; i < h; i++) {
      for (let j = 0; j < w; j++) {
        if (board[i][j]) {
          bfs(i, j, board, h, w);
          count++;
        }
      }
    }
    answer.push(count);
  }
  answer.pop();
  console.log(answer.join("\n"));
});

 

📍리뷰

- 8방 탐색? dxdy? 더 쉬운 주위 체크 방법을 익혀야 코드가 줄어들 것 같다