미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사과는 뛰어난 코딩 실력을 이용해 각 칸 (r, c)에 있는 미세먼지의 양을 실시간으로 모니터링하는 시스템을 개발했다. (r, c)는 r행 c열을 의미한다.
공기청정기는 항상 1번 열에 설치되어 있고, 크기는 두 행을 차지한다. 공기청정기가 설치되어 있지 않은 칸에는 미세먼지가 있고, (r, c)에 있는 미세먼지의 양은 Ar,c이다.
1초 동안 아래 적힌 일이 순서대로 일어난다.
미세먼지가 확산된다. 확산은 미세먼지가 있는 모든 칸에서 동시에 일어난다. - (r, c)에 있는 미세먼지는 인접한 네 방향으로 확산된다. - 인접한 방향에 공기청정기가 있거나, 칸이 없으면 그 방향으로는 확산이 일어나지 않는다. - 확산되는 양은 Ar,c/5이고 소수점은 버린다. 즉, ⌊Ar,c/5⌋이다. - (r, c)에 남은 미세먼지의 양은 Ar,c - ⌊Ar,c/5⌋×(확산된 방향의 개수) 이다.
공기청정기가 작동한다. - 공기청정기에서는 바람이 나온다. - 위쪽 공기청정기의 바람은 반시계방향으로 순환하고, 아래쪽 공기청정기의 바람은 시계방향으로 순환한다. - 바람이 불면 미세먼지가 바람의 방향대로 모두 한 칸씩 이동한다. - 공기청정기에서 부는 바람은 미세먼지가 없는 바람이고, 공기청정기로 들어간 미세먼지는 모두 정화된다.
다음은 확산의 예시이다.
왼쪽과 위쪽에 칸이 없기 때문에, 두 방향으로만 확산이 일어났다.
인접한 네 방향으로 모두 확산이 일어난다.
공기청정기가 있는 칸으로는 확산이 일어나지 않는다.
공기청정기의 바람은 다음과 같은 방향으로 순환한다.
방의 정보가 주어졌을 때, T초가 지난 후 구사과의 방에 남아있는 미세먼지의 양을 구해보자.
입력
첫째 줄에 R, C, T (6 ≤ R, C ≤ 50, 1 ≤ T ≤ 1,000) 가 주어진다.
둘째 줄부터 R개의 줄에 Ar,c (-1 ≤ Ar,c ≤ 1,000)가 주어진다. 공기청정기가 설치된 곳은 Ar,c가 -1이고, 나머지 값은 미세먼지의 양이다. -1은 2번 위아래로 붙어져 있고, 가장 윗 행, 아랫 행과 두 칸이상 떨어져 있다.
출력
첫째 줄에 T초가 지난 후 구사과 방에 남아있는 미세먼지의 양을 출력한다.
과정
시뮬레이션 문제이다.
미세먼지 분배와 공기청정기 바람 두가지로 나누어서 구현한다.
미세먼지의 확산은 확산이 완료된 새로운 배열을 만들어 원래의 배열의 값을 이용해 계산해준다.
import sys
input = sys.stdin.readline
r, c, t = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(r)]
for i in range(r):
if board[i][0] == -1:
ccw, cw = i, i+1 # ccw 반시계, cw 시계
break
def spread():
# 미세먼지 확산
dx = [1,-1,0,0]
dy = [0,0,1,-1]
new_board = [[0] * c for _ in range(r)]
new_board[ccw][0] = -1
new_board[cw][0] = -1
for x in range(r):
for y in range(c):
if board[x][y] > 0:
new_board[x][y] += board[x][y]
for d in range(4):
nx = x + dx[d]
ny = y + dy[d]
if 0 <= nx < r and 0 <= ny < c and board[nx][ny] != -1:
new_board[nx][ny] += board[x][y] // 5
new_board[x][y] -= board[x][y] // 5
return new_board
def rotate():
# 위쪽 순환: ccw 반시계 방향
for x in range(ccw-1, 0, -1):
board[x][0] = board[x-1][0]
for y in range(c-1):
board[0][y] = board[0][y+1]
for x in range(ccw):
board[x][-1] = board[x+1][-1]
for y in range(c-1, 0, -1):
board[ccw][y] = board[ccw][y-1]
# 아래쪽 순환: cw 시계 방향
for x in range(cw+1, r-1):
board[x][0] = board[x+1][0]
for y in range(c-1):
board[-1][y] = board[-1][y+1]
for x in range(r-1, cw, -1):
board[x][-1] = board[x-1][-1]
for y in range(c-1, 0, -1):
board[cw][y] = board[cw][y-1]
# 공기청정기에서 나온 바람은 미세 먼지가 없는 바람이므로 0으로 초기화
board[ccw][1] = 0
board[cw][1] = 0
for _ in range(t):
board = spread()
rotate()
# 결과 출력
ans = 0
for i in range(r):
for j in range(c):
if board[i][j] > 0:
ans += board[i][j]
print(ans)
한 줄씩 해석해보기
r, c, t = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(r)]
for i in range(r):
if board[i][0] == -1:
ccw, cw = i, i+1 # ccw 반시계, cw 시계
break
r 행 c열 t 초 를 입력받는다.
입력받은 숫자들로 r행만큼 board를 만들어 준다.
공기 청정기의 위치를 통해 순환을 정해주기 위해 -1을 입력받은 곳 위는 반시계 아래는 시계방향으로 설정한다.
def spread():
# 미세먼지 확산
dx = [1,-1,0,0]
dy = [0,0,1,-1]
new_board = [[0] * c for _ in range(r)]
new_board[ccw][0] = -1
new_board[cw][0] = -1
미세먼지 확산을 계산할 함수를 만들어준다.
동서남북으로 퍼지기 때문에 dx, dy를 만들어준다.
한번에 확산이 되기 때문에 새로운 보드를 만들어서 확산을 파악하고 그 후에 남은 배열과 합쳐준다.
new_board를 0으로 초기화하고 공기청정기 위치에 -1을 넣어준다.
for x in range(r):
for y in range(c):
if board[x][y] > 0:
new_board[x][y] += board[x][y]
for d in range(4):
nx = x + dx[d]
ny = y + dy[d]
if 0 <= nx < r and 0 <= ny < c and board[nx][ny] != -1:
new_board[nx][ny] += board[x][y] // 5
new_board[x][y] -= board[x][y] // 5
return new_board
원래 보드에 있는 값이 0보다 크다면 새로운 보드에 값을 넣어준다.
그 다음 해당 값의 동서남북을 모두 확인해준다.
만약 nx가 0이상 r미만이고 ny가 0이상 c미만, 원래 보드의 nx,ny값이 -1이 아니라면
새로운 보드의 nx ny 값에 원래 보드 위치의 값을 5로 나눈 나머지를 넣어준다
그다음 새로운 보드의 원래 위치 값에서 그만큼을 빼준다.
모든 보드를 확인 후 return한다.
def rotate():
# 위쪽 순환: ccw 반시계 방향
for x in range(ccw-1, 0, -1):
board[x][0] = board[x-1][0]
for y in range(c-1):
board[0][y] = board[0][y+1]
for x in range(ccw):
board[x][-1] = board[x+1][-1]
for y in range(c-1, 0, -1):
board[ccw][y] = board[ccw][y-1]
공기 순환은 미세먼지 확산 보드의 업데이트 이후에 진행한다.
공기청정기의 순환을 확인하는 함수를 만들어준다.
위쪽 순환과 아래쪽 순환을 나누어서 구현한다.
순환은 하나씩 업데이트 하는데 실제 흐름대로 업데이트 하는 경우 이전의 값이 사라지기 때문에 거꾸로 해주어야한다. 즉 시계방향으로 하나씩 업데이트 해준다.
공기청정기의 위치의 바로 위칸부터 업데이트 해준다.
보드의 [x][0] = [x-1][0] 즉 그 바로 위칸을 가져온다.
[0][y] = [0][y+1] 바로 오른쪽 값을 가져온다.
맨 끝 벽에 닿았을 경우 [x][-1] = [x+1][-1] 바로 아래 값을 가져온다.
[ccw][y] = [ccw][y-1] 바로 왼쪽 값을 가져온다.
# 아래쪽 순환: cw 시계 방향
for x in range(cw+1, r-1):
board[x][0] = board[x+1][0]
for y in range(c-1):
board[-1][y] = board[-1][y+1]
for x in range(r-1, cw, -1):
board[x][-1] = board[x-1][-1]
for y in range(c-1, 0, -1):
board[cw][y] = board[cw][y-1]
위쪽 순환의 반대로 코드를 짜준다.
# 공기청정기에서 나온 바람은 미세 먼지가 없는 바람이므로 0으로 초기화
board[ccw][1] = 0
board[cw][1] = 0
그 후 공기청정기에서 나온 바람은 미세먼지가 없는 바람이므로 0으로 초기화해준다.
for _ in range(t):
board = spread()
rotate()
t초만큼 보드를 spread()로 업데이트 해주고 rotate()함수를 돌려준다.
# 결과 출력
ans = 0
for i in range(r):
for j in range(c):
if board[i][j] > 0:
ans += board[i][j]
print(ans)
