(Python) 백준 17144번: 미세먼지 안녕!

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

17144번: 미세먼지 안녕!

 

python으로 제출했을때 시간초과

pypy3로 제출했을 때 통과

 

 

# Code

## 먼지 퍼뜨리기
def spread():
    for x in range(r):
        for y in range(c):
            if board[x][y] > 0:
                cnt = 0
                for i in range(4):
                    nx, ny = x+dx[i], y+dy[i]                        # 서, 동, 북, 남 방향
                    if not(0<=nx<r and 0<=ny<c): continue            # 범위를 벗어난다면.
                    if board[x][y] < 5: continue                     # 5보다 작다면 먼지가 퍼지지 않는다.
                    if (nx, ny) == (air_cleaner[0], 0): continue
                    if (nx, ny) == (air_cleaner[1], 0): continue
                    cnt = cnt + 1                                    # cnt 증가
                    board2[nx][ny] = board2[nx][ny] + board[x][y]//5 # board2에 퍼진 먼지량 추가
                board2[x][y] = board2[x][y] + board[x][y] - board[x][y]//5*cnt
 
 
def clean():
    ## 윗부분 반시계방향
    for i in range(air_cleaner[0]-2, -1, -1):
        board2[i+1][0] = board2[i][0]
    for i in range(1, c):
        board2[0][i-1] = board2[0][i]
    for i in range(1, air_cleaner[0]+1):
        board2[i-1][-1] = board2[i][-1]
    for i in range(c-2, 0, -1):
        board2[air_cleaner[0]][i+1] = board2[air_cleaner[0]][i]
    board2[air_cleaner[0]][1] = 0
    ## 아랫부분 시계방향
    for i in range(air_cleaner[1]+2, r):
        board2[i-1][0] = board2[i][0]
    for i in range(1, c):
        board2[-1][i-1] = board2[-1][i]
    for i in range(r-2, air_cleaner[1]-1, -1):
        board2[i+1][-1] = board2[i][-1]
    for i in range(c-2, 0, -1):
        board2[air_cleaner[1]][i+1] = board2[air_cleaner[1]][i]
    board2[air_cleaner[1]][1] = 0
 
 
if __name__ == '__main__':
    ## 행(r), 열(c), 시간(t)
    r, c, t = map(int, input().split())
    board = [list(map(int, input().split())) for _ in range(r)]
    # 공기 청정기 행 위치
    air_cleaner = []
    for i in range(r):
        if board[i][0] == -1: air_cleaner.append(i)
    # 서 동 북 남
    dx = (0, 0, -1, 1)
    dy = (-1, 1, 0, 0)
    # 1번 시행
    board2 = [[0]*c for _ in range(r)]
    spread()
    clean()
    ## t-1번 시행
    for time in range(t-1):
        board = board2.copy()
        board2 = [[0]*c for _ in range(r)]
        spread()
        clean()
    ## 전체 총합 구하기
    sumv = 0
    for i in range(r):
        for j in range(c):
            if board2[i][j] > 0: sumv = sumv + board2[i][j]
    print(sumv)