[백준 17144번] 미세먼지 안녕! - 자바스크립트(nodejs)

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

17144번: 미세먼지 안녕!

이번 구현문제는 빡구현 문제 수준이라 코드가 정말 길다... 더 줄일 수 있지만 푸느라 지쳐버렸다.

const readline = require('readline');

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});
let input = [];
rl.on('line', function (line) {
  input.push(line);
  if (input.length === +input[0].split(' ')[0] + 1) {
    rl.close();
  }
}).on('close', function () {
  let [R, C, time] = input.shift().split(' ').map(Number);
  let house = input.map((v) => v.split(' ').map(Number));
  const airCleanerIdx = house.map((v) => v[0]).indexOf(-1);

  let answer = 0;

  while (time) {
    house = diffusionDust(house); // 미세먼지 확장

    const antiClockwise = antiClockwiseRotation(house, airCleanerIdx); // 반시계 회전
    const clockwise = clockwiseRotation(house, airCleanerIdx); // 시계 회전

    house = antiClockwise.concat(clockwise); // 반시계 + 시계 배열 합치기

    answer = house.reduce((acc, cur) => acc + cur.reduce((a, c) => a + c), 0) + 2;

    time--;
  }

  console.log(answer);
});

function diffusionDust(arr) {
  const list = [];

  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr[i].length; j++) {
      if (arr[i][j] === 0 || arr[i][j] === -1) continue;

      const value = Math.floor(arr[i][j] / 5);
      let cnt = 0;

      if (i < arr.length - 1 && arr[i + 1][j] !== -1) {
        list.push([i + 1, j, value]);
        cnt++;
      }
      if (i > 0 && arr[i - 1][j] !== -1) {
        list.push([i - 1, j, value]);
        cnt++;
      }
      if (j < arr[i].length - 1 && arr[i][j + 1] !== -1) {
        list.push([i, j + 1, value]);
        cnt++;
      }
      if (j > 0 && arr[i][j - 1] !== -1) {
        list.push([i, j - 1, value]);
        cnt++;
      }

      arr[i][j] -= value * cnt;
    }
  }

  list.forEach((v) => {
    const [i, j, value] = v;

    arr[i][j] += value;
  });

  return arr;
}

function clockwiseRotation(arr, idx) {
  const clockwiseArr = [];

  for (let i = 0; i < arr.length; i++) {
    if (i > idx) {
      clockwiseArr.push(arr[i]);
    }
  }
  const value = [];

  value.push(...clockwiseArr[0].slice(1));
  for (let i = 1; i < clockwiseArr.length - 1; i++) value.push(clockwiseArr[i][clockwiseArr[1].length - 1]);
  value.push(...clockwiseArr[clockwiseArr.length - 1].reverse());
  clockwiseArr[clockwiseArr.length - 1].reverse();
  for (let i = clockwiseArr.length - 2; i > 0; i--) value.push(clockwiseArr[i][0]);

  value.pop();
  let x = 1;
  let y = 0;

  while (x < clockwiseArr[1].length - 1) {
    clockwiseArr[y][++x] = value.shift();
  }
  while (y < clockwiseArr.length - 1) {
    clockwiseArr[++y][x] = value.shift();
  }
  while (x > 0) {
    clockwiseArr[y][--x] = value.shift();
  }
  while (y > 0) {
    clockwiseArr[--y][x] = value.shift();
  }
  clockwiseArr[0][0] = -1;
  clockwiseArr[0][1] = 0;

  return clockwiseArr;
}

function antiClockwiseRotation(arr, idx) {
  const antiClockwiseArr = [];

  for (let i = 0; i < arr.length; i++) {
    if (i <= idx) {
      antiClockwiseArr.push(arr[i]);
    } else break;
  }

  const value = [];

  value.push(...antiClockwiseArr[idx].slice(1));
  for (let i = idx - 1; i > 0; i--) value.push(antiClockwiseArr[i][antiClockwiseArr[i].length - 1]);
  value.push(...antiClockwiseArr[0].reverse());
  antiClockwiseArr[0].reverse();
  for (let i = 1; i < idx; i++) value.push(antiClockwiseArr[i][0]);

  value.pop();
  let x = 1;
  let y = idx;

  while (x < antiClockwiseArr[1].length - 1) {
    antiClockwiseArr[y][++x] = value.shift();
  }
  while (y > 0) {
    antiClockwiseArr[--y][x] = value.shift();
  }
  while (x > 0) {
    antiClockwiseArr[y][--x] = value.shift();
  }
  while (y < idx) {
    antiClockwiseArr[++y][x] = value.shift();
  }

  antiClockwiseArr[idx][1] = 0;
  antiClockwiseArr[idx][0] = -1;

  return antiClockwiseArr;
}

diffusionDust 함수

- 미세먼지를 확장시키는 함수이다. 주의해야할 점은 각각 순서대로 상하좌우 판별 해주는 게 아니라, 0이었던 즉 이 전에 값이 없었던 곳에 확장으로 인해 새로운 값이 추가되어도 순회할 때 그 곳은 그냥 지나쳐야 한다. 

이렇게 나오고 끝내야되는데, 계속 진행하면 10 다음 9로 가서 다시 진행되고, 그 다음 (2,2)에 위치한 9에 가서 또 진행되어 엉망진창이 될 것이다.

 

diffusionDust함수에서 list 배열을 만들어 조건에 맞으면 i,j 인덱스와 value값을 넣고 마지막에 한꺼번에 가중치를 더해주었다.

 

clockwiseRotation 함수

 

antiClockwiseRotation 함수

 

- 각각 시계방향, 반시계방향으로 도는 배열을 return해주는 함수이다. 인덱스를 사용해서 할 수 있지만 그냥 돌려가면서 했다. 아마 최대 길이가 낮아 시간 복잡도를 생각하지 않고 그냥 shift()함수를 사용한 것 같다.

value를 하나씩 밀면 이 전 값을 참조할 수 없으므로 반대로 땡겨오는 방법도 생각해봤지만, 애초에 값이 명확해 그냥 4번만 돌리면 끝나리라 생각하고 작성하고, 다시 원래 배열에 한 칸씩 밀어서 추가해주었다.

 

 

main에서 airCleanerIdx는 공기청정기가 있는 인덱스를 의미한다. (어차피 가로는 무조건 0에 위치하므로)

그 후 time을 하나씩 빼가며 time이 0이될때까지 반복하며 값을 구해주면 끝이다.

 

(rotation함수가 각각 return해주는 값들을 concat으로 연결해 다시 house배열에 초기화했다.) 

 

 

아마 더 좋은 방법들이 많을 것이다. ex) 인덱스를 활용해 시계, 반시계를 한 함수에서 진행한다거나??

 

 

위 코드에서 아쉬운 점은 시계, 반시계 방향 대신 값을 땡겨오기 위해 반대로 밀어 value배열 필요없이 바로 값들을 삽입할 수 있는 방법을 채택하지 않은 것이다. (실제로 위 코드대로 진행하다보니 reverse등에서 fix를 많이 경험했다.)