풀이
시뮬레이션을 통한 구현 문제이다.
크게 구현해야 할 기능은 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)