[백준] 17144 - 미세먼지 안녕!(파이썬, Python)

https://pixabay.com/ko/photos/우산-햇빛-여자-비-빛-6239364/

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

17144번: 미세먼지 안녕!

 

해당 문제는 문제의 설명대로 1) 미세먼지를 확산시킨다. 2) 공기 청정기를 작동시킨다.  이 두 가지를 구현하는 문제이다.

 

저는 이 문제를 Python3로 제출할 때 시간 초과가 났습니다.

제 코드에 비효율적인 부분이 있는 거 같습니다.

 

하지만 구현 문제인 만큼 정확성을 확인하고 싶었고 아래의 글을 참고한 후 PyPy3로 제출을 했습니다.

 

https://www.acmicpc.net/board/view/41140

 

다행히 정확성은 문제가 없었습니다🥲

 

저처럼 Python3로 시간초과가 났음에도 코드의 정확성을 확인하고 싶은 분은 PyPy3로 제출하는 걸 권합니다.

 

전체 코드

import sys
from copy import deepcopy

R, C, T = map(int, sys.stdin.readline().strip().split())

mat = [ list(map(int, sys.stdin.readline().strip().split())) for e in range(R)]

cleanerPos = []
dustPos = []
answer = 0

for row in range(R):
    for col in range(C):
        if mat[row][col] == -1:
            cleanerPos = row
        elif mat[row][col] != 0:
            dustPos += [(row, col)]
            answer += mat[row][col]

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

zeroMat = [ [0] * C for _ in range(R) ]

for _ in range(T):
    emptyRoom = deepcopy(zeroMat)

    emptyRoom[cleanerPos-1][0] = -1
    emptyRoom[cleanerPos][0] = -1

    for r, c in dustPos:
        movingCnt = 0
        amountDust = mat[r][c]

        if amountDust // 5 > 0:
            for idx in range(4):
                newR = r+dy[idx]
                newC = c+dx[idx]
                
                if 0 <= newR < R and 0 <= newC < C and mat[newR][newC] != -1:
                    movingCnt += 1
                    emptyRoom[newR][newC] += amountDust // 5

        emptyRoom[r][c] += amountDust - (amountDust // 5) * movingCnt

    # 반시계 이동
    for r in range(cleanerPos -2, 0, -1):
        emptyRoom[r][0] = emptyRoom[r-1][0]

    emptyRoom[0] = emptyRoom[0][1:] + [0]

    for r in range(0, cleanerPos -1):
        emptyRoom[r][C-1] = emptyRoom[r+1][C-1]

    emptyRoom[cleanerPos-1] = [-1, 0] + emptyRoom[cleanerPos-1][1:-1]

    # 시계 이동
    for r in range(cleanerPos+1, R-1):
        emptyRoom[r][0] = emptyRoom[r+1][0]

    emptyRoom[R-1] = emptyRoom[R-1][1:] + [0]

    for r in range(R-1, cleanerPos, -1):
        emptyRoom[r][C-1] = emptyRoom[r-1][C-1]

    emptyRoom[cleanerPos] = [-1, 0] + emptyRoom[cleanerPos][1:-1]

    # 미세 먼지 위치 저장
    # 미세 먼지 무게 계산
    nextDustPos = []
    answer = 0

    for r in range(R):
        for c in range(C):
            # print(r, c)
            if emptyRoom[r][c] > 0:
                answer += emptyRoom[r][c]
                nextDustPos += [(r, c)]

    mat = deepcopy(emptyRoom)
    dustPos = nextDustPos[:]            

print(answer)