백준 17144 미세먼지 안녕!

계획

• 공기청정기 위치 파악하기
• 미세먼지 확산 시키기
  • 사방으로 퍼뜨림
  • 퍼진 미세먼지를 해당 위치의 기존 미세먼지에 합하는 방식으로 진행했더니, 퍼진 미세먼지를 중복으로 퍼뜨리는 경우가 생김
  • 빈 리스트를 만들어서 퍼진 미세먼지만 저장, 이후에 기존 리스트에 값을 더하는 방식으로 진행.
• 공기 순환 시키기
  • 위쪽은 반시계방향, 아래쪽은 시계방향으로 모서리만 순환한다.
  • 인덱스 에러 주의하기.

import sys
input = sys.stdin.readline
R, C, T = map(int, input().split())  # R 행, C 열, T 시간
map_lst = [list(map(int, input().split())) for _ in range(R)]

# 공기 청정기가 있는 행 파악하기
for i in range(R):
    if map_lst[i][0] == -1:
        air_row = i
        break

# 상 우 하 좌
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]

for _ in range(T):
    new_map_lst = []
    for _ in range(R):
        new_map_lst.append([0] * C)
    new_map_lst[air_row][0] = -1
    new_map_lst[air_row + 1][0] = -1
    # 미세먼지 확산 시키기
    for y in range(R):
        for x in range(C):
            if x == 0:
                if y == air_row or y == air_row + 1:
                    continue
            direct = 0
            diffuse = map_lst[y][x] // 5
            for k in range(4):
                nx = x + dx[k]
                ny = y + dy[k]
                if nx < 0 or ny < 0 or nx >= C or ny >= R or map_lst[ny][nx] == -1:
                    continue
                new_map_lst[ny][nx] = new_map_lst[ny][nx] + diffuse
                direct += 1
            new_map_lst[y][x] += map_lst[y][x] - direct * diffuse
    map_lst = list(new_map_lst)

    # 미세먼지 순환 시키기
    # # 맨 첫 번째 위치 주의

    # 위쪽 반시계
    # 왼쪽 열 내리고
    for i in range(air_row - 1, 0, -1):
        map_lst[i][0] = map_lst[i - 1][0]
    # 위쪽 행 왼쪽으로
    for i in range(C - 1):
        map_lst[0][i] = map_lst[0][i + 1]
    # 오른쪽 열 올리고
    for i in range(0, air_row):
        map_lst[i][-1] = map_lst[i + 1][-1]
    # 아래쪽 행 오른쪽으로
    for i in range(C - 1, 0, -1):
        map_lst[air_row][i] = map_lst[air_row][i - 1]
    map_lst[air_row][1] = 0
    # 아래쪽 시계
    # 왼쪽 열 위로
    for i in range(air_row + 2, R - 1):
        map_lst[i][0] = map_lst[i + 1][0]
    # 아래쪽 행 왼쪽으로
    for i in range(C - 1):
        map_lst[-1][i] = map_lst[-1][i + 1]
    # 오른쪽 열 아래로
    for i in range(R - 1, air_row, -1):
        map_lst[i][-1] = map_lst[i - 1][-1]
    # 위쪽 행 오른쪽으로
    for i in range(C - 1, 0, -1):
        map_lst[air_row + 1][i] = map_lst[air_row + 1][i - 1]
    map_lst[air_row + 1][1] = 0

    ans = 0
    for i in range(R):
        for j in range(C):
            ans += map_lst[i][j]
print(ans + 2) # 공기청정기 값 빼기

• 공기 청정기가 맨 위 또는 맨 아래있는 경우를 생각했었다. 근데 문제를 다시 읽으니 그런 경우는 입력으로 주어지지 않는다고 했다. 문제 잘 읽기..!
• Python으로는 시간초과가 발생하는데 PyPy로는 시간초과가 발생하지 않는다. 시간을 단축시키는 방법을 생각해봐야겠다.
• 8가지 반복문을 돌리면서 인덱스 주의해야겠다고 생각함.