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

문제 보기

이 문제는 시뮬레이션 문제이다.

처음에 문제를 훑고 나서 BFS 문제라고 생각했지만, 자세하게 문제를 읽어보니 나무 재테크와 비슷한 문제였다.

문제를 풀 때 주의할 점은 먼지를 확산시킬 때, 먼지를 확산시킬 칸들의 정보를 저장해두었다가, 모든 칸의 먼지의 양을 줄이고 나서 확산시켜야 한다. (이는 나무 재테크 문제에서처럼 똑같이 적용되는데, 각 칸을 순회할 때 먼지를 확산시켜 먼지의 양을 주변 칸에 더해버리면 다음 칸에서 확산시킬 먼지의 양에 영향을 끼친다.)

 

문제를 푼 로직은 다음과 같다.

1. 공기청정기의 위치를 찾는다. (8~12번째 줄)
2. 각 칸에서 미세먼지를 확산시킬 인접한 칸들을 찾고, 그만큼 현재 칸의 미세먼지의 양을 줄인다.
   동시에 인접한 칸들의 위치를 큐에 저장한다. (18~32번째 줄)
3. 큐에 저장된 칸에 미세먼지를 확산시킨다. (34~37번째 줄)
4. 공기청정기를 반 시계방향으로 작동시킨다. (39~51번째 줄)
5. 공기청정기를 시계방향으로 작동시킨다. (53~65번째 줄)
6. 주어진 시간 동안 1번부터 5번까지의 작업을 반복한다. (16번째 줄)
7. 미세먼지의 총합을 구한다. (67~71번째 줄)

 

import sys
from collections import deque
 
R, C, T = map(int, sys.stdin.readline().split())
board = [list(map(int, sys.stdin.readline().split())) for _ in range(R)]
air_purifier = list()
 
# find air purifier
for r in range(R):
    for c in range(C):
        if board[r][c] == -1:
            air_purifier.append((r, c))
 
# for a given time
directions = ((-1, 0), (0, 1), (1, 0), (0, -1))
for t in range(T):
    spread_q = deque()
    # for all dust on the map
    for r in range(R):
        for c in range(C):
            if board[r][c] > 0:
                spread_amount = board[r][c] // 5
                
                # for all directions
                for dr, dc in directions:
                    next_r = r + dr
                    next_c = c + dc
                    # if next block is available
                    if -1 < next_r < R and -1 < next_c < C:
                        if board[next_r][next_c] != -1:
                            board[r][c] -= spread_amount
                            spread_q.appendleft((next_r, next_c, spread_amount))
    
    # spread dust
    while spread_q:
        r, c, spread_amount = spread_q.pop()
        board[r][c] += spread_amount
 
    # air purifier works counter-clockwise
    base_r, base_c = air_purifier[0]
    for r in range(base_r - 1, -1, -1):
            board[r][base_c] = board[r - 1][base_c]
    for c in range(C - 1):
        board[0][c] = board[0][c + 1]
    for r in range(base_r):
        board[r][C - 1] = board[r + 1][C - 1]
    for c in range(C - 1, base_c, -1):
        if board[base_r][c - 1] == -1:
            board[base_r][c] = 0
        else:
            board[base_r][c] = board[base_r][c - 1]
        
    # air purifier works clockwise
    base_r, base_c = air_purifier[1]
    for r in range(base_r + 1, R - 1, 1):
        board[r][base_c] = board[r + 1][base_c]
    for c in range(C - 1):
        board[R - 1][c] = board[R - 1][c + 1]
    for r in range(R - 1, base_r, -1):
        board[r][C - 1] = board[r - 1][C - 1]
    for c in range(C - 1, base_c, -1):
        if board[base_r][c - 1] == -1:
            board[base_r][c] = 0
        else:
            board[base_r][c] = board[base_r][c - 1]
 
answer = 0
for r in range(R):
    for c in range(C):
        if board[r][c] > 0:
            answer += board[r][c]
print(answer)