[BOJ 17144] 미세먼지 안녕!(Python)

문제

미세먼지 안녕!

문제 해설

문제의 요구사항은 다음과 같습니다.

1. 미세먼지가 확산된다.
2. 공기 청정기가 가동된다.

• 다음과 같이 공기 청정기는 항상 위, 아래에서 2칸이상 띄워져 있어 Cycle이 존재하기 때문에 Cycle에 대해서 고민할 필요는 없습니다.

• 공기 청정기는 두칸을 차지하고, 항상 1열에 존재한다.

• 미세먼지가 먼저 확산되고, 그 후 공기 청정기가 가동된다.

미세먼지의 확산의 경우 한꺼번에 확산되야 하기 때문에 다른 값들과 겹치지 않게 큐와 같은 자료구조에 확산될 좌표와 양을 임시로 담아줘야 합니다.

공기청정기 가동의 경우 위쪽 부분과 아랫쪽 부분은 다른점이 방향밖에 없습니다. 그렇기 때문에 방향만 바꿔준다면 굳이 메소드를 하나 더 만들필요없이 재사용이 가능한 구조로 코드를 구현했습니다.

풀이 코드

import sys
from collections import deque

input = sys.stdin.readline
n, m, t = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
air = []  # 공기청정기 좌표, 위아래순

for i in range(n):
    if graph[i][0] == -1:
        air.append((i, 0))
# 미먼 확산
def spread():
    dx = -1, 0, 1, 0
    dy = 0, 1, 0, -1
    # 1. 맵에 존재하는 모든 미세먼지 큐에 삽입
    q = deque()
    for i in range(n):
        for j in range(m):
            if graph[i][j] > 0:
                # x, y, 미먼 양
                q.append((i, j, graph[i][j]))
    size = len(q)
    for _ in range(size):
        x, y, amount = q.popleft()
        spread_dust = amount // 5
        # 4방 탐색으로 확산될 곳을 찾는다.
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            # 범위 안이며 청정기랑 닿으면 안됨
            if 0 <= nx < n and 0 <= ny < m and graph[nx][ny] != -1:
                q.append((nx, ny, spread_dust))
                amount -= spread_dust
        # 확산된 먼지를 뺀 값을 다시 넣어줌.
        graph[x][y] = amount
    # 큐에는 현재 확산될 먼지밖에 없다. 모두 빼서 확산시킨다.
    while q:
        x, y, dust = q.popleft()
        graph[x][y] += dust


# 공기청정기 가동
def move_dust(x, y, command):
    # command = 0 -> 위쪽, 1-> 아랫쪽
    dx, dy = (0, 0, 0, 0), (0, 0, 0, 0)
    if command == 0:  # 오,위,왼,아래 순
        dx, dy = (0, -1, 0, 1), (1, 0, -1, 0)
    else:  # 오, 아래, 왼, 위 순
        dx, dy = (0, 1, 0, -1), (1, 0, -1, 0)
    dir, priv = 0, 0
    # 한바퀴 돌아 공기 청정기로 돌아올때까지 진행
    while True:
        nx = x + dx[dir]
        ny = y + dy[dir]
        # 범위 밖이면 방향을 틀어준다.
        if nx < 0 or nx >= n or ny < 0 or ny >= m:
            dir += 1
            continue
        # 종료조건
        if graph[nx][ny] == -1:
            break
        graph[nx][ny], priv = priv, graph[nx][ny]
        x, y = nx, ny


for _ in range(t):
    spread()
    for i in range(2):
        # 각각 위아래 청정기 가동
        move_dust(air[i][0], air[i][1], i)
answer = 0
for i in range(n):
    for j in range(m):
        if graph[i][j] > 0:
            answer += graph[i][j]
print(answer)