🦊 미세먼지 안녕!

1. 문제 링크

17144번: 미세먼지 안녕!

2. 코드

pypy3 146128kb 588ms

import sys

R, C, T = map(int, input().split())
CLEANER = [] #공기청정기 위치
MAP = []
for i in range(R):
    MAP.append(list(map(int, sys.stdin.readline().split())))
    for j in range(C):
        # 공기 청정기 좌표 저장
        if MAP[i][j] == -1:
            CLEANER.append([j, i])

# T초 동안 반복
for _ in range(T):
    # 먼지 위치 저장 (x, y, dust)
    DUST = []
    for i in range(R):
        for j in range(C):
            if MAP[i][j] > 0:
                DUST.append([j, i, MAP[i][j]])
    
    # 먼지 확산
    delta = [[1, 0], [0, -1], [-1, 0], [0, 1]]
    for x, y, dust in DUST:
        for dx, dy in delta:
            count = 0
            nx = x + dx
            ny = y + dy
            if 0 <= nx < C and 0 <= ny < R and MAP[ny][nx] != -1:
                MAP[y][x] -= dust // 5
                MAP[ny][nx] += dust // 5

    # 상단 공기 청정기 가동
    next_clean = []
    top = 1    
    for x, y in CLEANER:
        # 상단 여부
        direction = 0 # 0 ~ 3까지
        cur_x = x
        cur_y = y
        
        while True:
            dx, dy = delta[direction]
            nx = cur_x + dx
            ny = cur_y + dy

            # 다음칸을 현재칸의 먼지로 대체한 것을 저장
            if 0 <= nx < C and 0 <= ny < R:
                # 처음위치로 오면 break
                if MAP[ny][nx] == -1:
                    top = -1
                    break
            
                next_clean.append([nx, ny, max(0, MAP[cur_y][cur_x])])
                cur_x = nx
                cur_y = ny
            # 벽에 부딪히면 방향을 바꿈
            else:
                direction += top

    # 실제 반영
    for x, y, dust in next_clean:
        MAP[y][x] = dust

result = 0
for i in range(R):
    for j in range(C):
        if MAP[i][j] > 0:
            result += MAP[i][j]
print(result)

• 해설

  문제에서 제시한 조건에 맞게 DFS 로 구현