미세먼지 안녕! (백준 17144)

미세먼지 안녕! (백준 17144)

2024. 4. 23. 00:03ㆍ알고리즘

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

17144번: 미세먼지 안녕!

미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사

www.acmicpc.net

🚀문제 접근

과정을 두가지로 크게 나눌 수 있다. 하나는 확산 과정이고 하나는 공기 청정기를 가동하는 과정이다.

확산 과정

1. 미세먼지가 있는 영역을 구한다.

2. 각 위치마다 4방향 탐색을 한 후에 확산이 가능한 영역이면 미세먼지를 확산한다.

예외) 공기청정기가 있는 영역이나 범위를 벗어난 경우라면 확산시키지 못한다.

2-1. 이때 확산은 미세먼지가 있는 모든 영역에서 동시에 발생한다.

공기청정기 가동

위쪽 청정기는 반시계방향으로 순환하고 아래쪽 청정기는 시계방향으로 순환한다.

간단하게 과정을 요약하면 그렇게 어렵지는 않아보인다. 문제에서 주어진대로 잘 구현하면 된다.

let [a, ...map] = require('fs').readFileSync('input.txt').toString().trim().split('\n');

let [r, c, t] = a.split(' ').map(Number);

map = map.map((elem) => elem.split(' ').map(Number));

let totalDust;

while (t) {

// 1. 미세먼지가 있는 영역을 구한다.

// 이때 확산될 시 동시에 진행된다고 가정하므로 미세먼지 수치 / 5도 같이 저장해준다.

let dustPos = [];

let cleanerPos = [];

totalDust = 0;

for (let i = 0; i < r; i++) {

for (let j = 0; j < c; j++) {

if (map[i][j] > 0) {

dustPos.push([i, j, Math.floor(map[i][j] / 5)]);

totalDust += map[i][j];

} else if (map[i][j] === -1) cleanerPos.push([i, j]);

}

// 2. 각 위치마다 4방향 탐색 후, 확산이 가능한 영역이면 동시에 확산시킨다.

let dy = [-1, 0, 1, 0];

let dx = [0, 1, 0, -1];

for (let i = 0; i < dustPos.length; i++) {

let [y, x, amount] = dustPos[i];

let cnt = 0;

for (let j = 0; j < 4; j++) {

let ny = y + dy[j];

let nx = x + dx[j];

if (ny < 0 || ny >= r || nx < 0 || nx >= c || map[ny][nx] === -1) continue;

map[ny][nx] += amount;

cnt++;

}

map[y][x] -= amount * cnt;

}

미세먼지를 확산할 때 주의할 점은 동시에 확산된다는 점이고 확산되는 양은 현재 영역에 있는 값을 5로 나눈 값이다.

그리고 현재 영역은 확산된 영역의 갯수와 확산되는 양을 곱해서 빼주어야한다. 추가 연산이 필요하다.

이때 동시에 확산된다는 점을 무시하면 다른 미세먼지가 확산되어 원래 미세먼지의 값이 변형될 수 있고 이렇게 되면 올바른 값이 나오지 않는다. 따라서 미세먼지 영역을 계산할 때 미리 현재 영역의 확산되는 양을 구해준다.

// 3. 공기 청정기 가동

let i1 = cleanerPos[0][0];

let i2 = cleanerPos[1][0];

totalDust -= map[i1 - 1][0];

totalDust -= map[i2 + 1][0];

for (let i = i1 - 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 < i1; i++) map[i][c - 1] = map[i + 1][c - 1];

for (let i = c - 1; i > 0; i--) map[i1][i] = map[i1][i - 1];

map[i1][1] = 0;

for (let i = i2 + 1; 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 > i2; i--) map[i][c - 1] = map[i - 1][c - 1];

for (let i = c - 1; i > 0; i--) map[i2][i] = map[i2][i - 1];

map[i2][1] = 0;

t--;

공기청정기를 가동시키는 코드이다. 이 부분을 구현하는 것이 까다로웠다.

중요한 포인트는 복사시킬 값의 목적지를 정확하게 파악해야하는 것이다.

위쪽 청정기의 좌표가 i1이라고 했을 때 1번 순환과정을 코드로 옮긴 것이다.

복사시킬 값의 정확한 목적지를 파악하는 것이 중요하다.

🛠코드

공기청정기의 순환과정을 구현하는 것이 어려웠다. 어떤 값을 어디로 옮길 것인지 파악하는 것과 위쪽 청정기와 아래쪽 청정기를 나눠서 생각하는 방법을 배웠다. 너무 큰 범주의 문제는 작은 단위로 쪼개서 해결해보려고 노력하자.

function solution() {

let [a, ...map] = require('fs').readFileSync(0).toString().trim().split('\n');