🪴 Quartz 4.0

BOJ 17144 - 미세먼지 안녕!

5 min read

풀이

시뮬레이션을 통한 구현 문제이다.

크게 구현해야 할 기능은 2가지이다.

  1. 미세먼지의 확산

  2. 공기청정기의 바람

우선 미세먼지의 확산은 입력받은 2차원배열을 순회하며 0 보다 큰 정수들의 좌표를 저장해주면된다.

이후 저장된 좌표값들을 순회하며 확산 가능한 범위내로 확산한 뒤 확산지점의 양을 빠진만큼 빼주면된다.

이때 주의할 점이 있는데 만약 입력받은 그래프에서 그대로 위 기능을 구현할 경우 기존에 있던 미세먼지의 양에 영향을 끼쳐 동시에 확산하는 시뮬레이션을 구현할 수 없다.

때문에 new 라는 새로운 2차원 배열을 선언하고 좌표마다 생기는 값들을 더해주면된다.

미세먼지가 모두 확산된 뒤 공기청정기의 바람을 통해 시계방향, 반시계방향으로 순환한다.

먼저 앞서 입력받으며 저장해두었던 상단 공기청정기와 하단 공기청정기의 좌표를 기준으로 순환하는 형식을 구현해주면된다.

모든 순환이 종료되었을 때 공기청정기로 들어간 칸과 나온칸은 항상 0 이기 때문에 이에 맞게 배열을 업데이트해준다.

이후 new 값을 다시 graph 값에 대입해준 후 다음 반복을 실행한다.

모든 반복이 종료된 후 남아있는 미세먼지값을 리스트마다 sum 을 통해 출력해주면된다.

Python 으로 제출할 경우 시간초과가 일어나니 Pypy 로 제출하면된다.

소스코드

# 미세먼지 안녕!
from collections import deque
import sys
input = sys.stdin.readline
 
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
 
r, c, t = map(int, input().split())
graph = []
ux, uy = 0, 0
lx, ly = 0, 0
 
for i in range(r):
    line = list(map(int, input().split()))
    graph.append(line)
    for j in range(c):
        if line[j] == -1:
            if ux == 0:
                ux, uy = i, j
            else:
                lx, ly = i, j
 
for _ in range(t):
    new = [[0] * c for _ in range(r)]  # 미세먼지 확산 후 방 상태 초기화
    dust = []  # 현재 미세먼지의 위치
    for i in range(r):
        for j in range(c):
            if graph[i][j] > 0:
                dust.append((i, j))
 
    # 미세먼지 동시에 확산
    for x, y in dust:
        origin = graph[x][y]
        spread = origin//5
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < r and 0 <= ny < c and graph[nx][ny] != -1:
                new[nx][ny] += spread
                origin -= spread
        new[x][y] += origin
 
    # 위쪽 바람 반시계방향 순환
    udx = [-1, 0, 1, 0]
    udy = [0, 1, 0, -1]
    temp = 0
    iux = ux-1
    iuy = uy
 
    for i in range(4):
        while True:
            nux = iux + udx[i]
            nuy = iuy + udy[i]
            if 0 <= nux <= ux and 0 <= nuy < c:
                new[iux][iuy] = new[nux][nuy]
                iux, iuy = nux, nuy
            else:
                break
    new[ux][uy] = 0
    new[ux][uy+1] = 0
 
    # 아래쪽 바람 반시계방향 순환
    ldx = [1, 0, -1, 0]
    ldy = [0, 1, 0, -1]
    temp = 0
    ilx = lx+1
    ily = ly
 
    for i in range(4):
        while True:
            nlx = ilx + ldx[i]
            nly = ily + ldy[i]
            if lx <= nlx < r and 0 <= nly < c:
                new[ilx][ily] = new[nlx][nly]
                ilx, ily = nlx, nly
            else:
                break
    new[lx][ly] = 0
    new[lx][ly+1] = 0
 
    graph = new  # 방상태 업데이트
 
ans = 0
for g in graph:
    ans += sum(g)
 
print(ans)

References

Graph View