백준 js - 4963번

<문제>

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

 

 

 

<문제 핵심>

 

1. 테스트케이스가 여러개인 경우 어떻게 처리해야하는지 막혔음

-> while 내부에서 입력을 받음으로써 마지막 0 0 입력값에 도달 했을 때 while문 탈출 

-> 각각의 w, h를 받은다음 h 만큼 한줄씩 밑으로 이동하여 그래프를 채운다.

 

2. bfs를 활용하는 문제이고 대각선으로도 이동할 수 있도록 암묵적 그래프 생성

 

 

<문제 풀이과정 및 순서도>

while문 내부에서 흘러가는 로직을 정리하고자 한다.

const input = require("fs")
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "./input.txt")
  .toString()
  .trim()
  .split("\n");

while (input.length > 1) {
  const [w, h] = input.shift().split(" ").map(Number);
  let temp = h;
  const graph = [];
  const visited = Array.from({ length: h }, () => Array(w).fill(false));
  while (temp > 0) {
    graph.push(input.shift().split(" ").map(Number));
    temp--;
  }
  let count = 0;

  const bfs = (x, y) => {
    const dir = [
      [1, 0],
      [-1, 0],
      [0, 1],
      [0, -1],
      [1, 1],
      [1, -1],
      [-1, 1],
      [-1, -1],
    ];
    const queue = [[x, y]];
    visited[x][y] = true;

    while (queue.length) {
      const [x, y] = queue.shift();
      for (let i = 0; i < 8; i++) {
        const [newX, newY] = [x + dir[i][0], y + dir[i][1]];
        if (newX >= 0 && newX < h && newY >= 0 && newY < w) {
          if (graph[newX][newY] === 1 && visited[newX][newY] === false) {
            visited[newX][newY] = true;
            queue.push([newX, newY]);
          }
        }
      }
    }
  };

  for (let i = 0; i < h; i++) {
    for (let j = 0; j < w; j++) {
      if (graph[i][j] === 1 && !visited[i][j]) {
        bfs(i, j);
        count++;
      }
    }
  }

  console.log(count);
}

 

✅ 마지막 입력값 0 0 에 도달 할 때까지 각각의 테스트 케이스의 w, h를 받는다.

✅ 입력받은 h만큼 한 줄씩 내려가면서 그래프를 생성한다.(이 부분 막혔음)

 

✅ 0,0부터 시작하는 좌표를 기점으로 그래프의 값이 1(섬)인지 그리고 방문을 안했다면 bfs함수를 호출한다.

-> bfs함수를 호출하게 되면 인접 노드를 탐색하기 때문에 count를 증가시킨다.

✅ 암묵적 그래프는 대각선의 이동도 고려해야 하므로 총 8가지의 방향 배열이 나온다.

✅ 암묵적 그래프의 배열 값과 기존 x, y값을 더한 좌표를 새로운 좌표로 구하고 그래프 상에서 새로운 좌표가 1인지(섬인지) 그리고 방문안했는지를 판단한다. -> 방문 안했다면 방문 처리해주고 큐에 삽입

 

<전체 코드>

const input = require("fs")
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "./input.txt")
  .toString()
  .trim()
  .split("\n");

while (input.length > 1) {
  const [w, h] = input.shift().split(" ").map(Number);
  let temp = h;
  const graph = [];
  const visited = Array.from({ length: h }, () => Array(w).fill(false));
  while (temp > 0) {
    graph.push(input.shift().split(" ").map(Number));
    temp--;
  }
  let count = 0;

  const bfs = (x, y) => {
    const dir = [
      [1, 0],
      [-1, 0],
      [0, 1],
      [0, -1],
      [1, 1],
      [1, -1],
      [-1, 1],
      [-1, -1],
    ];
    const queue = [[x, y]];
    visited[x][y] = true;

    while (queue.length) {
      const [x, y] = queue.shift();
      for (let i = 0; i < 8; i++) {
        const [newX, newY] = [x + dir[i][0], y + dir[i][1]];
        if (newX >= 0 && newX < h && newY >= 0 && newY < w) {
          if (graph[newX][newY] === 1 && visited[newX][newY] === false) {
            visited[newX][newY] = true;
            queue.push([newX, newY]);
          }
        }
      }
    }
  };

  for (let i = 0; i < h; i++) {
    for (let j = 0; j < w; j++) {
      if (graph[i][j] === 1 && !visited[i][j]) {
        bfs(i, j);
        count++;
      }
    }
  }

  console.log(count);
}

 

<리팩토링 해본 부분>

✅ for of 문을 통해 배열 요소를 가져오고 dx, dy로 변경 -> x+dx, y+dy로 변경

while (queue.length) {
      const [x, y] = queue.shift();
      for (let [dx, dy] of dir) {
        const [newX, newY] = [x + dx, y + dy];
        if (newX >= 0 && newX < h && newY >= 0 && newY < w) {
          if (graph[newX][newY] === 1 && visited[newX][newY] === false) {
            visited[newX][newY] = true;
            queue.push([newX, newY]);
          }
        }
      }
 }