[백준] 16719번 (python 파이썬)

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

 

구현문제이다.

1초 동안 아래 적힌 일이 순서대로 일어난다.

1. 미세먼지가 확산된다. 확산은 미세먼지가 있는 모든 칸에서 동시에 일어난다.
   • (r, c)에 있는 미세먼지는 인접한 네 방향으로 확산된다.
   • 인접한 방향에 공기청정기가 있거나, 칸이 없으면 그 방향으로는 확산이 일어나지 않는다.
   • 확산되는 양은 Ar,c/5이고 소수점은 버린다.
   • (r, c)에 남은 미세먼지의 양은 Ar,c - (Ar,c/5)×(확산된 방향의 개수) 이다.
2. 공기청정기가 작동한다.
   • 공기청정기에서는 바람이 나온다.
   • 위쪽 공기청정기의 바람은 반시계방향으로 순환하고, 아래쪽 공기청정기의 바람은 시계방향으로 순환한다.
   • 바람이 불면 미세먼지가 바람의 방향대로 모두 한 칸씩 이동한다.
   • 공기청정기에서 부는 바람은 미세먼지가 없는 바람이고, 공기청정기로 들어간 미세먼지는 모두 정화된다.

 

해당 규칙을 순서대로 적용하면 쉽게 풀수있다.

 

여기서 미세먼지가 확산될때 0, 0부터 r, c까지 미세먼지가 있는 곳을 계산 해주는데 계산은 똑같은 List를 하나더 만들어서 계산은 복사한 List에만 해주고 마지막에 복사한 List를 반환해줬다.

 

공기청정기에의한 공기 순환은 8방향 반복문으로 구현하였다. ( 더쉬운 방법이 있을텐데... )

 

import sys
input = sys.stdin.readline

r, c, t = map(int, input().split(' '))
graph = [list(map(int, input().split(' '))) for _ in range(r)]

d_x = [-1, 0, 1, 0]
d_y = [0, 1, 0, -1]


def diffusion(graph: list):
    new_graph = [temp[:] for temp in graph]

    for i in range(r):
        for j in range(c):

            if graph[i][j] == 0 or graph[i][j] == -1:
                continue

            now_dust = graph[i][j]
            cnt = 0
            for k in range(4):
                n_x = i + d_x[k]
                n_y = j + d_y[k]

                if n_x < 0 or n_x >= r or n_y < 0 or n_y >= c:
                    continue
                if graph[n_x][n_y] == -1:
                    continue

                cnt += 1

            div_dust = now_dust // 5
            for k in range(4):
                n_x = i + d_x[k]
                n_y = j + d_y[k]

                if n_x < 0 or n_x >= r or n_y < 0 or n_y >= c:
                    continue
                if graph[n_x][n_y] == -1:
                    continue

                new_graph[n_x][n_y] += div_dust

            new_graph[i][j] -= (div_dust * cnt)

    return new_graph


def work_air():
    f_x = None
    for i in range(r):
        if graph[i][0] == -1:
            f_x = i
            break
    s_x = f_x + 1

    up_prev_dust = graph[f_x][1]
    down_prev_dust = graph[s_x][1]
    for j in range(1, c):
        if graph[f_x][j - 1] == -1:
            graph[f_x][j] = 0
            graph[s_x][j] = 0
        else:
            temp = graph[f_x][j]
            temp2 = graph[s_x][j]
            graph[f_x][j] = up_prev_dust
            graph[s_x][j] = down_prev_dust
            up_prev_dust = temp
            down_prev_dust = temp2

    for i in range(f_x - 1, -1, -1):
        temp = graph[i][c - 1]
        graph[i][c - 1] = up_prev_dust
        up_prev_dust = temp

    for i in range(s_x + 1, r):
        temp2 = graph[i][c-1]
        graph[i][c -1] = down_prev_dust
        down_prev_dust = temp2

    for j in range(c-2, -1, -1):
        temp = graph[0][j]
        temp2 = graph[r-1][j]
        graph[0][j] = up_prev_dust
        graph[r-1][j] = down_prev_dust
        up_prev_dust = temp
        down_prev_dust = temp2

    for i in range(1, f_x):
        temp = graph[i][0]
        graph[i][0] = up_prev_dust
        up_prev_dust = temp

    for i in range(r-2, s_x, -1):
        temp2 = graph[i][0]
        graph[i][0] = down_prev_dust
        down_prev_dust = temp2

for i in range(t):
    graph = diffusion(graph)
    work_air()

answer = 0

for i in range(r):
    for j in range(c):
        if graph[i][j] == -1:
            continue
        else:
            answer += graph[i][j]

print(answer)