[BaekJoon] 16932 번 모양 만들기 문제 - (nodejs)

문제 번호 :  16932 번

문제 바로가기 ☞  https://www.acmicpc.net/problem/16932

---

 

<<< 문제 내용 >>>

---

 

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

const [N, M] = input[0].split(" ").map(Number);
let board = [];
let groupSize = [];
let answer = [];

for (let i = 1; i < N + 1; i++) {
  board.push(input[i].split(" ").map(Number));
}

let visited = Array.from(Array(N), () => new Array(M).fill(false));
const dy = [-1, 1, 0, 0];
const dx = [0, 0, -1, 1];

/* 각 그룹 별로 묶여진 개수 표현 */
const bfs = (y, x, groups) => {
  let cnt = 0;
  let queue = [[y, x]];
  visited[y][x] = true;
  board[y][x] = groups;

  while (queue.length) {
    [y, x] = queue.shift();
    cnt++;

    for (let i = 0; i < 4; i++) {
      let ny = y + dy[i];
      let nx = x + dx[i];

      if (ny < 0 || ny >= N || nx < 0 || nx >= M) continue;

      if (!visited[ny][nx] && board[ny][nx] === 1) {
        queue.push([ny, nx]);
        board[ny][nx] = groups;
        visited[ny][nx] = true;
      }
    }
  }

  return cnt;
};

let count = 1;
for (let i = 0; i < N; i++) {
  for (let j = 0; j < M; j++) {
    if (board[i][j] === 1 && !visited[i][j]) {
      // 이때, groupSize = [group 1번의 도시개수, group 2번의 도시개수, ... ];
      // 이게 핵심입니다. 그래야 다음에 0 마다 상하좌우 숫자 판단해서 탐색 더 안해두 됩니다.
      groupSize.push(bfs(i, j, count));
      count += 1;
    }
  }
}

// 위에 말했듯이 이제 상하좌우만 판단해서 탐색해줍니다.
const fourWay = (y, x, temp) => {
  for (let i = 0; i < 4; i++) {
    let ny = y + dy[i];
    let nx = x + dx[i];

    if (ny < 0 || ny >= N || nx < 0 || nx >= M) continue;

    if (board[ny][nx] !== 0) {
      temp.add(board[ny][nx]);
    }
  }
};

for (let i = 0; i < N; i++) {
  for (let j = 0; j < M; j++) {
    if (board[i][j] === 0) {
      //만약 중복된 수가 있다면 같은 그룹이니 Set으로 중복을 제거하고 계산합니다.
      let temp = new Set();
      let sum = 0;
      fourWay(i, j, temp);
      temp.forEach((el) => {
        sum += groupSize[el - 1];
      });
      answer.push(sum + 1);
    }
  }
}

console.log(Math.max(...answer));

 

 

도움이 되셨다면 공감 부탁드립니다.