17144번 - 미세먼지 안녕!

1️⃣ 구현

 

✏️ 풀이 과정

문제에서 묘사하는 상황을 파트 별로 모듈로 만들어 그대로 재현하는 문제입니다. 구현해야하는 모듈은 2개가 있습니다. 하나는 먼지를 확산시키는 모듈이고 다른 하나는 공기청정기를 구동하는 모듈입니다.

 

먼지 확산 단계는 상하좌우 4방향 중 이동할 수 있는 칸이 있을 경우 그 칸의 1/5을 버림한 만큼의 먼지를 옮기는 작업입니다. 주의해야 할 점은 문제에서 모든 칸에서 확산이 동시에 일어나고 있다고 설명하기 때문에 다른 칸의 확산 결과가 이후의 확산에서 반영되지 않아야 한다는 것입니다. 이를 위해서 먼저 먼지의 이동량을 다른 배열에 저장하고 이동 가능 여부를 판단하면서 원본 배열을 업데이트하는 방식을 사용했습니다. 사방탐색은 상수 배열을 통해 for문으로 진행했습니다. 칸이 범위를 벗어났거나 공기청정기가 거기에 있을 경우 확산되지 않도록 if문을 사용하여 처리했습니다.

 

다음 단계는 공기청정기의 가동입니다. 공기청정기가 가동되면 공기청정기가 위치한 각 두 칸을 중심으로 사각형을 그리며 먼지를 한 칸씩 이동시킵니다. 결과로 먼지 한 칸이 사라지고 반대편에서 0이 하나 나오게 됩니다. 배열의 원소를 삭제하고 당기는 것과 똑같은 상황이지만 위치가 네 방향으로 항상 바뀌기 때문에 부호나 인덱스에 주의해서 구현해야 합니다. 먼지가 이동하는 화살표 방향으로 한 칸씩 당기고 끝에 0을 추가하면 구현이 완료됩니다. 부호 실수를 하게 될 경우 디버깅이 매우 어렵기 때문에 주의해야 합니다.

 

두 모듈의 구현이 완료되었다면 확산과 정화 단계를 T번만큼 반복하면 결과를 얻을 수 있습니다. 남은 먼지의 양을 구하기 위해 처음에 입력을 받을 때 모든 먼지의 합을 더하고 공기청정기 가동 시에 사라지는 만큼을 빼주는 방법을 사용했습니다.

 

⏱ 시간 복잡도

확산 단계에서는 전체 칸을 사방 탐색을 할 때 O(RC)만큼의 시간 복잡도, 청정 단계에서는 O(R+C)만큼의 시간 복잡도가 나옵니다. 합보다는 곱이 일반적으로 크기 때문에 O(RC)라고 생각할 수 있으며 T번 반복하기 때문에 O(TRC)의 시간 복잡도가 나옵니다. R과 C는 50까지, T는 1000까지 가능하기 때문에 4 * 50 * 50 * 1000 + 4 * 2 * (50 + 50) * 1000 까지의 계산량을 추정할 수 있고 시간 내에 구동될 것을 예측할 수 있습니다.

 

💻 코드

JavaScript

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

const [R, C, T] = input[0].split(" ").map(Number);
let sum = 0,
    num;
const map = Array.from(Array(R), (_, i) => {
    return input[i + 1].split(" ").map((val) => {
        num = Number(val);
        sum += num;
        return num;
    });
});
sum += 2;

let purifier;
for (let i = 0; i < R; i++) {
    if (map[i][0] === -1) {
        purifier = i;
        break;
    }
}

const dr = [-1, 1, 0, 0];
const dc = [0, 0, -1, 1];

let nr, nc;

const check = (nr, nc, map) => {
    if (nr < 0 || nc < 0 || nr >= R || nc >= C || map[nr][nc] === -1) {
        return false;
    }
    return true;
};

const diffuse = (map) => {
    let dust = Array.from(Array(R), (_, i) =>
        map[i].map((val) => {
            return parseInt(val / 5);
        })
    );
    for (let i = 0; i < R; i++) {
        for (let j = 0; j < C; j++) {
            for (let k = 0; k < 4; k++) {
                nr = i + dr[k];
                nc = j + dc[k];
                if (!check(nr, nc, map)) {
                    continue;
                }
                map[nr][nc] += dust[i][j];
                map[i][j] -= dust[i][j];
            }
        }
    }
};

const purify = (map) => {
    sum -= map[purifier - 1][0];
    for (let i = purifier - 1; i > 0; i--) {
        map[i][0] = map[i - 1][0];
    }
    for (let i = 0; i < C - 1; i++) {
        map[0][i] = map[0][i + 1];
    }
    for (let i = 0; i < purifier; i++) {
        map[i][C - 1] = map[i + 1][C - 1];
    }
    for (let i = C - 1; i > 1; i--) {
        map[purifier][i] = map[purifier][i - 1];
    }
    map[purifier][1] = 0;

    sum -= map[purifier + 2][0];
    for (let i = purifier + 2; i < R - 1; i++) {
        map[i][0] = map[i + 1][0];
    }
    for (let i = 0; i < C - 1; i++) {
        map[R - 1][i] = map[R - 1][i + 1];
    }
    for (let i = R - 1; i > purifier + 1; i--) {
        map[i][C - 1] = map[i - 1][C - 1];
    }
    for (let i = C - 1; i > 1; i--) {
        map[purifier + 1][i] = map[purifier + 1][i - 1];
    }
    map[purifier + 1][1] = 0;
};

for (let i = 0; i < T; i++) {
    diffuse(map);
    purify(map);
}

console.log(sum);