[백준/G4] 17144 미세먼지 안녕!

foresec·2024년 6월 26일

백준

목록 보기

16/23

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

시간복잡도

O(TRC)해서 O(N**3)

풀이

미세먼지 확산
공기청정기 작동으로 인한 이동 및 회수

이렇게 2개의 단계로 이루어진다

여기서 주의해야할 점은 자리 하나씩 값이 변경 되며 누적되면 안되므로 별도의 배열을 생성해서 여기에 변경된 값을 저장한 뒤 이 배열을 반환해야하는 것이다

최종코드

const dx = [1, 0, -1, 0];
const dy = [0, -1, 0, 1];

function rotateUpside(maxX, C, x, y) {
  if (x === maxX && y < C - 1) {
    y++;
  } else if (x !== 0 && y === C - 1) {
    x--;
  } else if (x === 0 && y > 0) {
    y--;
  } else if (x < maxX && y === 0) {
    x++;
  }
  return [x, y];
}

function rotateDownside(minX, R, C, x, y) {
  if (x === minX && y < C - 1) {
    y++;
  } else if (x < R - 1 && y === C - 1) {
    x++;
  } else if (x === R - 1 && y > 0) {
    y--;
  } else if (x !== minX && y === 0) {
    x--;
  }
  return [x, y];
}

function moveDust(R, C, arr, base) {
  // 작동 시 1칸씩 이동, 공기청정기로 들어간 미세먼지는 정화됨
  let movedArr = new Array(R);
  for (let i = 0; i < R; i++) {
    movedArr[i] = new Array(C).fill(0);
  }

  const [up, down] = base;

  // 위쪽(반시계)
  for (let i = up[0]; i >= 0; i--) {
    for (let j = 0; j < C; j++) {
      if (arr[i][j] > 0) {
        let [newX, newY] = rotateUpside(up[0], C, i, j);
        // 공기청정기의 위치와 같으면 제외
        if (newX === up[0] && newY == up[1]) continue;
        movedArr[newX][newY] = arr[i][j];
      }
    }
  }
  // 아래쪽(시계)
  for (let i = down[0]; i < R; i++) {
    for (let j = 0; j < C; j++) {
      if (arr[i][j] > 0) {
        let [newX, newY] = rotateDownside(down[0], R, C, i, j);
        // 공기청정기의 위치와 같으면 제외
        if (newX === down[0] && newY == down[1]) continue;
        movedArr[newX][newY] = arr[i][j];
      }
    }
  }
  // 공기청정기 위치 표기
  movedArr[up[0]][up[1]] = -1;
  movedArr[down[0]][down[1]] = -1;

  return movedArr;
}

function diffusion(R, C, arr, base) {
  // 5분의 1의 양만큼 4방향으로 확산하며 남은 양은 기존양 - 확산된 양 * 방향갯수
  // (칸 or 공기청정기일 경우 X)
  let diffusedArr = new Array(R);
  for (let i = 0; i < R; i++) {
    diffusedArr[i] = new Array(C).fill(0);
  }

  const [up, down] = base;

  for (let x = 0; x < R; x++) {
    for (let y = 0; y < C; y++) {
      if (arr[x][y] > 0) {
        let dirCnt = 0;
        let val = Math.floor(arr[x][y] / 5);

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

          if (nx < 0 || nx >= R || ny < 0 || ny >= C) continue;

          if (arr[nx][ny] === -1) continue;

          // 먼지 퍼짐
          diffusedArr[nx][ny] += val;
          dirCnt += 1;
        }
        // 기존값 업데이트
        if (dirCnt > 0) {
          diffusedArr[x][y] += arr[x][y] - dirCnt * val;
        }
      }
    }
  }
  // 공기청정기 위치 표기
  diffusedArr[up[0]][up[1]] = -1;
  diffusedArr[down[0]][down[1]] = -1;

  return diffusedArr;
}

// T초 후 방에 남아있는 미세먼지의 양
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./17144.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");

const [R, C, T] = input[0].split(" ").map(Number);
let arr = [];
let airCleaner = [];

for (let i = 1; i <= R; i++) {
  let row = input[i].split(" ").map((val, j) => {
    let num = Number(val);
    if (num === -1) airCleaner.push([i - 1, j]);
    return num;
  });
  arr.push(row);
}

let currentArr = arr;
for (let t = 0; t < T; t++) {
  // 1. 미세먼지 확산(한번에 일어남)
  currentArr = diffusion(R, C, currentArr, airCleaner);
  // 2. 공기청정기 이동 및 회수
  currentArr = moveDust(R, C, currentArr, airCleaner);
}

// 공기청정기 자리 미리 +2
let ans = 2;
for (let i = 0; i < R; i++) {
  for (let j = 0; j < C; j++) {
    ans += currentArr[i][j];
  }
}

console.log(ans);

15940kb 456ms

고민점 1 (함수의 분리와 파라미터)

지금까지는 프로그래머스 대비형태로 함수를 분리해서 매번 매개변수를 전부 넘기고 리턴해오는 형태로 풀고 있긴한데.. 사실 백준 형식으로 받아오는 데이터 형식으로는 R, C, arr 등이 전역변수라 함수에 넘기지 않고도 쓸 수 있다.

함수에 넘기는 매개변수 형태를 유지했을 때 어떤 변수가 쓰이고 변수 이름을 새롭게 정의하면서 깔끔하다는 면에서 장점도 있지만

함수에 넘기는 매개변수가 너무 많아져도 결국 성능에 영향이 간다는 단점이 있다

이런 부분에서 어떤 방법이 더 적절할지는 고민할 필요가 있어보임

고민점 2

const arr1 = new Array(R).fill(0).map(() => new Array(C).fill(0)); 
// 18636kb	576ms	node.js

const arr2 = Array.from({ length: R }, () => Array.from({ length: C }, () => 0)); 
// 15732kb	828ms	node.js


let arr3 = new Array(R);
for (let i = 0; i < R; i++) {
  arr3[i] = new Array(C).fill(0);
} 
// 	15932kb	508ms	node.js