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

문제

출처 : www.acmicpc.net/problem/17144

17144번: 미세먼지 안녕!

구사과는 미세먼지를 제거하기위해 공기청정기를 설치하려고한다.

공기 청정기는 항상 1번 열에 설치되어있고, 크기는 두행을 차지한다. 공기청정기가 없는 칸에는 미세먼지가 있다.

 

미세먼지는 매초 마다 확산을 하는데, 확산되는 양은 다음과같다.
확산되는 양 : Ay,x / 5

y,x에 남는양 : Ay,x - (Ay,x/5 * 확산된 방향의 개수)

 

미세먼지가 확산을 한 이후에는 공기청정기가 작동하여 미세먼지를 위는 반시계방향, 아래는 시계방향으로 이동시킨다. 이때, 미세먼지가 공기청정기로 들어가면 해당 미세먼지는 사라진다.

 

방의 세로길이 R, 가로길이 C, 모니터링할 시간 T가 주어졌을때, T초가 지난 후 구사과의 방에 남아있는 미세먼지의 양을 구하는 문제다.

 

풀이

T의 최댓값이 1000, R과 C의 최댓값이 각각 50 이다. 매초 모든칸(250)을 두번씩 본다해도, 1000 * 500 = 500000이라 시간초과가 나지않는다. 침착하게 구현해야 하는 문제였다.

 

문제에서 요구하는 그대로 구현하면 되는데, 문제는 미세먼지의 확산과 이동이 모든 미세먼지에 대해서 동시에 일어난다는것이다.

따라서, 하나를 미리 확산시키거나 이동시키면 안되고 한번에 처리해줘야한다. 이런 한번에 이동?이 필요한 문제는 덱이나 큐 혹은 스택과 같은 자료구조를 이용해서 풀면 비교적 편하게 풀수있다. 

 

우선 미세먼지를 확산 시키는대로 필요한 과정을 크게 3가지로 나눴다.

1. 미세먼지를 확산시키는 과정

2. 위쪽 공기청정기의 좌표를 기준으로 미세먼지를 이동시키는 과정

3. 아래쪽 공기청정기의 좌표를 기준으로 미세먼지를 이동시키는 과정

 

위 과정을 순서대로 구현했는데, 

1. 확산시켜야할 미세먼지에 대해서 확산시킨다. 이때 모든 미세먼지는 동시에 확산되어야하므로(하나를 미리 확산시키면 이미 확산된 미세먼지가 한번 더 확산될수있기때문) 우선, 미세먼지를 확산시킨 상태를 바로 업데이트 하는게 아닌, queue에 집어넣는다. 모든 해당하는 미세먼지를 queue에 집어넣었으면, queue가 빌때 까지 확산시켜줬다.

 

2,3 번 미세먼지를 이동시킨다. 이때, 모든 미세먼지를 동시에 이동시켜야 하므로(하나를 먼저 이동시키면, 왼쪽,위 와 같이 이동방향이 겹치는 부분에 대해서 미세먼지가 두번 이동할 위험이있음) 마찬가지로 바로 이동상태를 업데이트 해주는게 아닌, queue에 집어넣어줬다. 모두 queue에 집어넣어줬다면 queue가 빌때까지 미세먼지를 이동시켜준다.(이때, 공기청정기 위치에 이동시켜야한다면 업데이트 하지않고 pop만 해준다)

 

위 과정을 T까지 반복시켜주고 남아있는 미세먼지를 구하면 답이나온다.

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/17144%20%EB%AF%B8%EC%84%B8%EB%A8%BC%EC%A7%80%20%EC%95%88%EB%85%95!/main.cpp

devxb/JJUNalgo