[BOJ] 1743 음식물 피하기


  • BOJ 음식물 피하기 문제 풀이입니다.

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

const [N, M, K] = input
  .shift()
  .split(" ")
  .map((item) => +item);
const coord = input.map((item) => item.split(" ").map((item) => +item));

// 배열 초기화
let matrix = [...Array(N + 1)].map((x) => Array(M + 1).fill("."));

// 해당 좌표를  # 로 변경
for (let i = 0; i < K; i++) {
  matrix[coord[i][0]][coord[i][1]] = "#";
}

function solution(N, M, matrix) {
  let start = [];

  // # 에 해당하는 위치를 시작점으로
  for (let r = 0; r < N + 1; r++) {
    for (let c = 0; c < M + 1; c++) {
      if (matrix[r][c] === "#") {
        start.push([r, c]);
      }
    }
  }

  //위, 오른쪽, 아래, 왼쪽
  const dr = [-1, 0, 1, 0];
  const dc = [0, 1, 0, -1];

  let result = 0;

  for (let i = 0; i < start.length; i++) {
    let stack = [[start[i][0], start[i][1]]];
    const newMatrix = [...matrix.map((item) => [...item])];
    let count = 1;

    while (stack.length) {
      const [r, c] = stack.shift();
      newMatrix[r][c] = -1;

      for (let i = 0; i < 4; i++) {
        const nr = r + dr[i];
        const nc = c + dc[i];

        if (-1 < nr && nr < N + 1 && -1 < nc && nc < M + 1) {
          if (newMatrix[nr][nc] === "#") {
            stack.push([nr, nc]);
            newMatrix[nr][nc] = -1;
            count += 1;
          }
        }
      }
    }

    result = count > result ? count : result;
  }

  console.log(result);
}

solution(N, M, matrix);

Reference









© 2020. by dkmqflx

Powered by dkmqflx