nxm 보드
공기청정기는 항상 1열에 설치되어 있고, 두 행을 차지.
공기 청정기가 설치되지 않은 칸에는 미세먼지 존재. (각 칸의 값이 미세먼지 크기)
1-1. 미세먼지는 확산된다. 확산은 모든 칸에서 동시에 발생.
1-2. (r,c)에 있는 미세먼지는 인접한 네 방향으로 확산된다.
import sys
sys.stdin = open("input.txt", "rt")
# nxm 보드
# 공기청정기는 항상 1열에 설치되어 있고, 두 행을 차지.
# 공기 청정기가 설치되지 않은 칸에는 미세먼지 존재. (각 칸의 값이 미세먼지 크기)
# 1-1. 미세먼지는 확산된다. 확산은 모든 칸에서 동시에 발생.
# 1-2. (r,c)에 있는 미세먼지는 인접한 네 방향으로 확산된다.
# - 인접한 방향에 공기청정기가 있거나, 칸이 없으면 해당 방향으로 확산되지 않음.
# 1-3. 확산되는 양은 각 칸의 값 / 5, 소수점 버림.
# 2. 공기청정기 작동
# 위쪽 공기청정기는 반시계방향으로 순환, 아래쪽 공기청정기는 시계방향으로 순환.
dx = [-1,0,1,0]
dy = [0,1,0,-1]
def isInner(x,y):
if 0<=x<n and 0<=y<m:
return True
return False
def step1(x,y,g,temp):
cnt = 0
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if not isInner(nx,ny):
continue
if g[nx][ny] == -1: continue # 미세먼지
cnt += 1
val = int(g[x][y] / 5)
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if not isInner(nx,ny): continue
if g[nx][ny] == -1: continue
temp[nx][ny] += val
temp[x][y] -= val * cnt
# step1. 확산
def 확산(g):
temp = [arr[:] for arr in g]
for x in range(n):
for y in range(m):
if g[x][y] > 0:
step1(x,y,g,temp)
return temp # 확산 적용한 보드 다시 반환.
# step2. 공기청정기
def 미세먼지순환(g):
# 1. 위쪽 공기청정기
x,y = 공기청정기[0][0], 공기청정기[0][1] # 위쪽 공기청정기 좌표
tx,ty = x,y
dir = 0 # 시작 방향
L = 0
while True:
if (x,y) == (tx,ty) and L == 3: # 방향전환 + 시작위치 돌아옴
break
nx = x + dx[dir]
ny = y + dy[dir]
if not (0<=nx<=tx and 0<=ny<m): # 범위 !
L += 1
dir = (dir + 1) % 4
nx = x + dx[dir]
ny = y + dy[dir]
g[x][y] = g[nx][ny]
x,y = nx,ny # 위치 이동
g[tx][ty] = 0
g[tx][ty+1] = 0
# 여기서 중요했던게 사라지는 부분 뿐만 아니라, 미세먼지 위치 부분 역시 0이든 -1이든 초기화해줬어야 함.
# 2. 아래쪽 공기청정기
x,y = 공기청정기[1][0], 공기청정기[1][1]
tx,ty = x,y
dir = 2 # 시작 방향
L = 0
while True:
if (x,y) == (tx,ty) and L == 3:
break
nx = x + dx[dir]
ny = y + dy[dir]
if not (tx<=nx<n and 0<=ny<m):
L += 1
dir = (dir + 3) % 4
nx = x + dx[dir]
ny = y + dy[dir]
g[x][y] = g[nx][ny]
x,y = nx,ny # 위치 변경
g[tx][ty] = 0
g[tx][ty+1] = 0
n,m,T = map(int, input().split()) # T초 후의 미세먼지 양 구하기
g = [list(map(int, input().split())) for _ in range(n)]
공기청정기 = []
for i in range(n):
if g[i][0] == -1: # 공기청정기
공기청정기.append((i,0))
def 보드출력(g):
print("======================")
for x in range(n):
for y in range(m):
print(g[x][y], end = " ")
print()
for i in range(T):
# 1. 확산
g = 확산(g)
# 2. 순환
미세먼지순환(g)
# 보드출력(g)
res = 0
for i in range(n):
for j in range(m):
if g[i][j] > 0:
res += g[i][j]
print(res)
어떻게 풀 수 있을까 ?
문제의 조건에 맞게 미세먼지를 확산시키고 난 후에, 미세먼지를 순환하는 것을 입력 받은 시간만큼 반복하면 된다.
확산을 표현할 때는 이전 상태와 현재 상태가 섞이지 않도록, map을 2개 두어서 구현하는 것이 좋다.
미세먼지 순환은 어떻게 ? 공기청정기로 들어가는 곳부터 시작하면 temp변수 없이 해결 가능.
실수했던 부분은 공기청정기의 순환을 구현하는 부분.
nx,ny 범위를 좌표 전체로 둘 게 아니라, 미세먼지 위 아래 각각에 맞춘 가동범위로 짰어야 함. 이 부분을 실수했음.