서론

시뮬레이션 문제입니다.
먼지 확산 까지는 빠르게 구현하였으나, 공기청정기를 통한 먼지 이동에서 시간이 오래걸린 문제였습니다.
첫 번째 코드는 직접 구현. deque를 통해 좌우 이동은 rotate, 상하 이동은 반복문을 통해 해결하였습니다.
두 번째 코드는 다른 분들의 코드를 참고하여 작성했습니다.
두 코드의 시간 차이는 조금 나네요.

난이도

골드 4

---

문제

조건

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

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

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

1. 미세먼지가 확산된다. 확산은 미세먼지가 있는 모든 칸에서 동시에 일어난다.

• (r, c)에 있는 미세먼지는 인접한 네 방향으로 확산된다.
• 인접한 방향에 공기청정기가 있거나, 칸이 없으면 그 방향으로는 확산이 일어나지 않는다.
• 확산되는 양은 Ar,c/5이고 소수점은 버린다. 즉, ⌊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초가 지난 후 구사과 방에 남아있는 미세먼지의 양을 출력한다.

예시

예제 입력 1

7 8 1  
0 0 0 0 0 0 0 9
0 0 0 0 3 0 0 8
-1 0 5 0 0 0 22 0
-1 8 0 0 0 0 0 0
0 0 0 0 0 10 43 0
0 0 5 0 15 0 0 0
0 0 40 0 0 0 20 0

예제 출력 1

188

예제 입력 2

7 8 2
0 0 0 0 0 0 0 9
0 0 0 0 3 0 0 8
-1 0 5 0 0 0 22 0
-1 8 0 0 0 0 0 0
0 0 0 0 0 10 43 0
0 0 5 0 15 0 0 0
0 0 40 0 0 0 20 0

예제 출력 2

186

---

풀이

1. 확산은 상하좌우 1칸씩 탐색하여 (현재 칸의 먼지 / 5, 내림) 만큼 따로 저장
   (딕셔너리를 이용하여 먼지가 이동할 칸의 좌표와 이동할 먼지의 값 저장)
2. 주변으로 확산된 먼지의 값만큼 현재 좌표의 먼지 빼기
3. 확산이 끝나면 확산이 일어난 좌표(주변으로 확산된 만큼을 뺀 후)에 다른 칸에서 확산된 먼지 값 더하기
   (딕셔너리에서 저장한 값을 여기서 추가)
4. 공기청정기의 위아래 좌표를 찾아 상단 부분 하단 부분 따로 회전

deque를 이용한 행렬 테두리 회전

import sys
from collections import deque, defaultdict
input = sys.stdin.readline

def spread(): # 먼지 확산
    for x in range(r):
        for y in range(c):
            if board[x][y] > 0:
                dust = board[x][y] // 5

                for dx, dy in dxy:
                    nx = x + dx
                    ny = y + dy

                    if 0 <= nx < r and 0 <= ny < c and board[nx][ny] != -1:
                        spread_dust[(nx, ny)] += dust # 주변 한 칸 먼지 확산(따로 저장)
                        board[x][y] -= dust # 확산된 만큼 원래 자리 먼지 감소
    
    for k, v in spread_dust.items(): # 확산된 먼지 좌표를 확인하여 최종적으로 더해주기
        board[k[0]][k[1]] += v

def upper_area(r): # 공기 청정기 위쪽 회전
    for x in range(r - 1, 0, -1): # 1열 아래로 이동
        board[x][0] = board[x - 1][0] 

    board[0].rotate(-1) # 가장 위쪽 행 왼쪽으로 이동

    for x in range(r): # 끝열 위쪽으로 이동
        board[x][c - 1] = board[x + 1][c - 1]

    board[r].rotate(1) # 공기청정기쪽 행 오른쪽으로 이동

def lower_area(r): # 공기 청정기 아래쪽 회전
    for x in range(r, len(board) - 1): # 1열 위로 이동
        board[x][0] = board[x + 1][0]

    board[-1].rotate(-1) # 마지막 행 왼쪽으로 이동

    for x in range(len(board) - 1, r, -1): # 끝열 아래쪽으로 이동
        board[x][c - 1] = board[x - 1][c - 1]

    board[r].rotate(1) # 공기청정기쪽 행 오른쪽으로 이동

def purify(): # 공기 순환
    for x in range(2, r):
        if board[x][0] == -1: 	# 공기청정기를 찾은 경우
            upper_area(x)		# 위쪽 순환
            lower_area(x + 1)	# 아래쪽 순환

            for i in range(2):	# 순환 후 공기청정기와 오른쪽 초기화
                board[x][i] = i - 1
                board[x + 1][i] = i - 1
            return

r, c, t = map(int, input().split())
board = [deque(map(int, input().split())) for _ in range(r)]
dxy = [(0, 1), (0, -1), (1, 0), (-1, 0)]

for _ in range(t):
    spread_dust = defaultdict(int)
    spread()
    purify()

print(sum([sum(i) for i in board]) + 2)	# 모두 더한 후 공기청정기로 인해 2 더하기

실행 결과

반복문을 이용한 행렬 테두리 회전

# 코드에 없는 나머지 부분은 동일

def upper_area(top): 	# 공기 청정기 위쪽 회전
    prev, d = 0, 1 		# 이전 값 저장할 prev, 방향을 나타낼d(우측부터 이동)
    x, y = top, 1 		# 공기청정기 위쪽의 좌표(오른쪽부터 돌 예정이기 때문에 y는 1)

    while True:
        nx = x + dxy[d][0] # 이동할 좌표 설정
        ny = y + dxy[d][1]

        if x == top and y == 0: # 공기청정기 위치로 오면(모두 돌면) 종료
            break
        if not 0 <= nx < r or not 0 <= ny < c: # 모서리에 다다르면(이동할 좌표가 범위를 벗어나면)
            d = (d - 1) % 4 # 방향 전환 후 continue
            continue

        board[x][y], prev = prev, board[x][y] # 이전 위치의 먼지를 현재 위치로 옮김 + 현재 위치 다시 저장
        x, y = nx, ny # 다음 좌표로 이동

def lower_area(bottom): # 공기 청정기 아래쪽 회전(위와 동일한 방식이나 방향만 다름)
    prev, d = 0, 1
    x, y = bottom, 1

    while True:
        nx = x + dxy[d][0]
        ny = y + dxy[d][1]

        if x == bottom and y == 0:
            break
        if not 0 <= nx < r or not 0 <= ny < c:
            d = (d + 1) % 4
            continue

        board[x][y], prev = prev, board[x][y]
        x, y = nx, ny

board = [list(map(int, input().split())) for _ in range(r)] # deque -> list
dxy = [(-1, 0), (0, 1), (1, 0), (0, -1)] # 상, 우, 하, 좌 순서로 이동

실행 결과