[파이썬 | BOJ | 17144] 미세먼지 안녕!

https://www.acmicpc.net/problem/17144

17144번: 미세먼지 안녕!

문제

미세문지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사과는 뛰어난 코딩 실력을 이용해 각 칸 (r, c)에 있는 미세먼지의 양을 실시간으로 모니터링하는 시스템을 개발했다. (r, c)는 r행 c열을 의미한다.

공기청정기는 항상 1번 열에 설치되어 있고, 크기는 두 행을 차지한다. 공기청정기가 설치되어 있지 않은 칸에는 미세먼지가 있고, (r, c)에 있는 미세먼지의 양은 Ar,c이다.

1초 동안 아래 적힌 일이 순서대로 일어난다.

1. 미세먼지가 확산된다. 확산은 미세먼지가 있는 모든 칸에서 동시에 일어난다.
   • (r, c)에 있는 미세먼지는 인접한 네 방향으로 확산된다.
   • 인접한 방향에 공기청정기가 있거나, 칸이 없으면 그 방향으로는 확산이 일어나지 않는다.
   • 확산되는 양은 Ar,c/5이고 소수점은 버린다.
   • (r, c)에 남은 미세먼지의 양은 Ar,c - (Ar,c/5)×(확산된 방향의 개수) 이다.
2. 공기청정기가 작동한다.
   • 공기청정기에서는 바람이 나온다.
   • 위쪽 공기청정기의 바람은 반시계방향으로 순환하고, 아래쪽 공기청정기의 바람은 시계방향으로 순환한다.
   • 바람이 불면 미세먼지가 바람의 방향대로 모두 한 칸씩 이동한다.
   • 공기청정기에서 부는 바람은 미세먼지가 없는 바람이고, 공기청정기로 들어간 미세먼지는 모두 정화된다.

다음은 확산의 예시이다.

왼쪽과 오른쪽에 칸이 없기 때문에, 두 방향으로만 확산이 일어났다.

인접한 네 방향으로 모두 확산이 일어난다.

공기청정기가 있는 칸으로는 확산이 일어나지 않는다.

공기청정기의 바람은 다음과 같은 방향으로 순환한다.

방의 정보가 주어졌을 때, 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초가 지난 후 구사과 방에 남아있는 미세먼지의 양을 출력한다.

풀이

시뮬레이션 문제이다.

일단 각각의 미세먼지가 확산되는 시뮬레이션을 구성하고,

또한 바람의 방향에 따라 시계, 반시계로 회전하는 알고리즘을 구성하면 된다.

 

확산 되는 시뮬레이션을 할 때 주의해야 할 점은, 원래 board에다가 이중 for문으로 탐색해가면서 확산시키면, 왼쪽 상단에 위치한 먼지가 확산되어서 다음 먼지의 확산양에 영향을 끼칠 수 있다는 점이다. 미세먼지의 확장은 동시에 일어나는 알고리즘으로 구성해야 하므로, 일단 temp배열을 만들어서 거기서 하나의 미세먼지가 확산하는 것을 더해 나가되, 원래 미세먼지에는 영향을 끼치지 않도록 알고리즘을 구성해야 한다. 

그리고 나서 모든 r, c를 탐색하고 나서 temp배열을 원래 board에 복사해야 한다.

 

다음 바람에 따른 회전을 구성하는 것은 편한대로 구현하면 되는데, for문의 증가방향과 배열의 값 이동은 서로 반대여야 한다. 예를들어 i가 0부터 N까지 증가한다고 할때 arr[i+1] = arr[i]이라고 알고리즘을 구성하면 arr[0]값이 모조리 복사되기 때문이다.

 

 

# [파이썬 | BOJ | 17144] 미세먼지 안녕!
 
import sys
read = sys.stdin.readline
# 상 하 좌 우
d = [[-1, 0], [1, 0], [0, -1], [0, 1]]
cleaner = []
 
def myPrint(arr):
    for a in arr:
        print(a)
    print()
 
def copy(board, temp):
    for r in range(R):
        for c in range(C):
            board[r][c] = temp[r][c]
 
def diffusion():
    temp = [[0 for _ in range(C)] for _ in range(R)]
    for r in range(R):
        for c in range(C):
            if board[r][c] == 0:
                continue
            if board[r][c] == -1:
                cleaner.append(r)
                continue
            temp[r][c] += board[r][c]
            for i in range(4):
                nr, nc = r + d[i][0], c + d[i][1]
                if 0 <= nr < R and 0 <= nc < C and board[nr][nc] != -1:
                    subval = (board[r][c] // 5)
                    temp[nr][nc] += subval
                    temp[r][c] -= subval
    temp[cleaner[0]][0] = -1
    temp[cleaner[1]][0] = -1
    
    copy(board, temp)
 
def rotate():
    temp = board[0][0]
    for r in range(R):
        for c in range(C):
            if r == 0 and 1 <= c < C:
                board[r][c-1] = board[r][c]
            elif c == C-1 and 1 <= r <= cleaner[0]:
                board[r-1][c] = board[r][c]
 
            if r == R-1 and 1 <= c < C:
                board[r][c-1] = board[r][c]
            elif c == 0 and cleaner[1]+1 <= r < R:
                board[r-1][c] = board[r][c]
 
    for r in reversed(range(R)):
        for c in reversed(range(C)):
            if r == cleaner[0] and 0 <= c < C-1:
                board[r][c+1] = board[r][c]
            elif c == 0 and 0 <= r < cleaner[0]:
                board[r+1][c] = board[r][c]
 
            if r == cleaner[1] and 0 <= c < C-1:
                board[r][c+1] = board[r][c]
            elif c == C-1 and cleaner[1] <= r < R-1:
                board[r+1][c] = board[r][c]
 
    board[1][0] = temp
    board[cleaner[0]][1] = 0
    board[cleaner[0]][0] = 0
    board[cleaner[1]][0] = 0
    board[cleaner[1]][1] = 0
    
    #myPrint(board)
    
def dust():
    ret = 0
    for r in reversed(range(R)):
        for c in reversed(range(C)):
            ret += board[r][c]
    return ret
 
R, C, T = map(int, read().split())
board = []
for _ in range(R):
    board.append(list(map(int, read().split())))
 
for t in range(T):
    diffusion()
    rotate()
    ans = dust()
 
print(ans)