백준 17144 < 미세먼지 안녕! > JavaScript

📍문제 링크

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

17144번: 미세먼지 안녕!

 

📍알고리즘 분류

- 구현

- 시뮬레이션

 

📍문제 풀이

- 좌표 평면에 미세먼지 분포가 주어진다

- 2 * 1 크기의 공간을 차지하는 공기청정기가 공기를 순환시킨다

- 동시에 미세먼지는 상하좌우로 확산한다

- N 초 후 공간의 전체 미세먼지 총량을 구하라

 

어려운 구현문제였다..

 

1. 좌표 평면의 0열에서 공기 청정기 상부의 좌표 k 를 찾아서 저장하기

2. 순환 기능 구현

- 상하좌우 움직임을 구현할 부분

 

- 좌표들의 이동을 어떻게 구현? => 새로운 배열 만들어서 거기에 넣고 리턴하기
- new map에 old map의 값을 넣기
- 상부 하부 말고 상하좌우로 묶기

 

3. 확산 기능 구현

- 상 하 좌 우 인덱스가 유효 범위내에 있고, 값이 -1이 아니면,
- Math.floor(val / 5) 을 상 하 좌 우 에 더하고
- 배출한 방향 수 * 배출량을 빼기

 

이 때도 현재 변화가 간섭을 일으키지않도록

new map 과 old map을 활용한다

new map은 old map을 deep copy 하여 사용

 

📍코드 (JavaScript)

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

const input = [];

// 0으로 채워진 2차원 배열을 리턴하는 함수
const newMap = (r, c) => {
  return Array.from({ length: r }, (_) => Array.from({ length: c }, (_) => 0));
};

// 확산 기능
const spread = (oldmap, r, c) => {
  // 이차원 배열을 deep copy
  const newmap = oldmap.map((row) => [...row]);
  for (let i = 0; i < r; i++) {
    for (let j = 0; j < c; j++) {
      // 5보다 작으면 확산 X, 이동만 수행
      if (oldmap[i][j] > 4) {
        const value = Math.floor(oldmap[i][j] / 5);
        // 상
        if (i > 0 && oldmap[i - 1][j] !== -1) {
          newmap[i][j] -= value;
          newmap[i - 1][j] += value;
        }
        // 하
        if (i < r - 1 && oldmap[i + 1][j] !== -1) {
          newmap[i][j] -= value;
          newmap[i + 1][j] += value;
        }
        // 좌
        if (j > 0 && oldmap[i][j - 1] !== -1) {
          newmap[i][j] -= value;
          newmap[i][j - 1] += value;
        }
        // 우
        if (j < c - 1 && oldmap[i][j + 1] !== -1) {
          newmap[i][j] -= value;
          newmap[i][j + 1] += value;
        }
      }
    }
  }
  return newmap;
};

// 1칸 순환 기능
const circulate = (oldmap, r, c, k) => {
  const newmap = newMap(r, c);

  for (let i = 0; i < r; i++) {
    for (let j = 0; j < c; j++) {
      // 우로 이동
      if ((i === k || i === k + 1) && j >= 2) {
        newmap[i][j] = oldmap[i][j - 1];
      }
      // 좌로 이동
      else if ((i === 0 || i === r - 1) && j < c - 1) {
        newmap[i][j] = oldmap[i][j + 1];
      }
      // 위로 이동
      else if ((i < k && j === c - 1) || (i > k + 1 && i < r - 1 && j === 0)) {
        newmap[i][j] = oldmap[i + 1][j];
      }
      // 아래로 이동
      else if ((i > 0 && i < k && j === 0) || (i > k + 1 && j === c - 1)) {
        newmap[i][j] = oldmap[i - 1][j];
      } else {
        newmap[i][j] = oldmap[i][j];
      }
    }
  }
  // 공기청정기 배출구 0으로 만들기
  newmap[k][1] = 0;
  newmap[k + 1][1] = 0;
  // 공기 청정기 위치 고정
  newmap[k][0] = -1;
  newmap[k + 1][0] = -1;
  return newmap;
};

rl.on("line", (line) => {
  input.push(line);
}).on("close", () => {
  const [R, C, T] = input.shift().split(" ").map(Number);
  let board = input.map((row) => row.split(" ").map(Number));

  let kRow = 0;
  for (let i = 2; i < R - 2; i++) {
    if (board[i][0] === -1) {
      kRow = i;
      break;
    }
  }

  for (let i = 0; i < T; i++) {
    // 확산 하고 이동
    board = spread(board, R, C);
    board = circulate(board, R, C, kRow);
  }
  let answer = 2;
  board.forEach((row) => (answer += row.reduce((acc, cur) => acc + cur, 0)));
  console.log(answer);
});

 

📍리뷰

- 구현이 복잡했지만 구현해야할 기능을 잘게 나눠서 세부적으로 진행하니 괜찮았다

- 사용할 함수를 전역에 정의하여 모듈화했더니, 중간 중간에 테스트하기가 너무 편리!!