17144: 미세먼지 안녕!

풀이 시간

• 1h 28m
• 처음에 공기청정기가 작동하는 부분을 시계방향으로 deque에 1차원으로 저장하고 popleft(), append(0) 해주는 방식으로 구현하려 했으나 코드를 짜다보니 너무 꼬여서 이에 대해 dx, dy로 이동하는 방식의 아이디어를 참고했다

구현 방식

1. 미세먼지 확장

• 미세먼지를 확장할 때 주의해야하는 건 기존에 미세먼지가 있던 칸의 값이 확장 도중 갱신되면 안된다는 점이다
• 따라서 diff 2차원 리스트를 선언하여 확산되는 위치에 대한 값을 저장해준다
• 탐색이 끝나고 나서 diff의 값을 board에 추가해준다

2. 공기청정기 작동

• 이 부분은 dx, dy의 index를 이용해 시계방향 또는 반시계방향으로 한 칸씩 밀어주는 아이디어를 참고했다
• 공기청정기의 오른쪽 옆칸부터 시작. while문을 돌면서 현재 좌표가 공기청정기일 경우 종료
• nx == R or ny == C or nx == -1 or ny == -1인 경우는 현재 좌표가 꼭짓점이었던 경우이므로 direction을 바꿔주어야함 (direction을 시계방향 또는 반시계방향으로 update)
• 현재 값에 이전 값을 넣어주고, 이전 값을 현재 값으로 갱신
• 현재 좌표를 다음 좌표로 update

소스 코드

import sys
from collections import deque

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

def move_up(mr1, mc1):
    direction = 1
    before = 0
    x, y = mr1, 1
    while True:
        nx = x + dx[direction]; ny = y + dy[direction]
        if nx == R or ny == C or nx == -1 or ny == -1: #현재 좌표가 꼭짓점
            direction = (direction+1) % 4
            continue
        if x == mr1 and y == 0: #현재 좌표가 공기청정기
            break
        board[x][y], before = before, board[x][y]
        x, y = nx, ny

def move_down(mr2, mc2):
    direction = 1
    before = 0
    x, y = mr2, 1
    while True:
        nx = x + dx[direction]; ny = y + dy[direction]
        if nx == R or ny == C or nx == -1 or ny == -1: #현재 좌표가 꼭짓점
            direction = (direction-1) % 4
            continue
        if x == mr2 and y == 0: #현재 좌표가 공기청정기
            break
        board[x][y], before = before, board[x][y]
        x, y = nx, ny

R, C, T = map(int, sys.stdin.readline()[:-1].split())
board = []
machine = []
for r in range(R):
    tmp = list(map(int, sys.stdin.readline()[:-1].split()))
    for c in range(C):
        if tmp[c] == -1:
            machine.append((r, c))
    board.append(tmp)

for _ in range(T):
    # 미세먼지 확산
    diff = [[0] * C for _ in range(R)]
    for x in range(R):
        for y in range(C):
            if board[x][y] > 0:
                cnt = 0
                for i in range(4):
                    nx = x + dx[i]; ny = y + dy[i]
                    if 0 <= nx < R and 0 <= ny < C:
                        if board[nx][ny] != -1:
                            diff[nx][ny] += board[x][y] // 5 #확산되는 위치는 일단 diff에만 저장
                            cnt += 1
                board[x][y] -= (board[x][y] // 5) * cnt
    
    #저장했던 diff를 한번에 더해줌
    for i in range(R):
        for j in range(C):
            board[i][j] += diff[i][j]

    # 공기청정기 작동
    move_up(machine[0][0], machine[0][1])
    move_down(machine[1][0], machine[1][1])

# 전체 미세먼지 양 출력
result = 0
for r in range(R):
    result += sum(board[r])
print(result + 2)

결과