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

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

17144번: 미세먼지 안녕!

최근 알고리즘을 다시 풀기 시작했습니다! 감각을 다시 익힐 겸 해서 구현 위주로 풀고 있다 보니 죄다 삼성 기출문제네요.

• 이번 문제도 어김없이.. 제가 문제를 읽고 처음 든 생각은 두 가지였습니다. 
  • 순서대로 일어난다 라는 조건이 있으니 조건 순서대로 구현을 해봐야겠다.
  • 구현은 죄다 그래프를 쓰는 문제니 익숙해지자. 예를 들면 한 칸씩 움직인다던가 bfs, dfs 등등...
• 자 그럼 풀어보겠습니다. 먼저 미세먼지가 확산되는 함수와 공기청정기가 작동하는 함수를 나눠서 생각했습니다.
• 미세먼지가 확산되는 구현은 인접한 네 방향으로 먼저 확산이 일어나고 남은 미세먼지를 구하는 함수, 그리고 네 방향으로부터 받은 미세먼지를 구하는 함수로 나눠서 (들어온 미세먼지 양) - (나간 미세먼지 양)으로 한 칸 미세먼지 양을 구했습니다.
• 공기 청정기가 작동했을 때는, 위쪽 반시계 방향으로 작동할 때와, 아래쪽 시계 방향으로 작동할 때는 나눠서 각각 구해줬고, 여기서 기억해야 할 점 중 하나는 함수를 이동한다던가 변경할 일이 있으면 temp를 사용하던가 deepcopy를 사용해서 원래 주어진 graph값이 변하지 않도록 하는게 중요합니다.
• 함수 작성이 끝났으면 이제 graph를 입력받고, deepcopy로 graph를 복사해준 뒤, for문을 돌려서 공기청정기가 아닌 칸들을 대상으로 미세먼지 함수를 실행시켜 미세먼지 값을 모두 저장해준 뒤, 공기청정기 함수를 실행시켜 미세먼지 위치 이동까지 시켜줍니다.
• 변경이 모두 끝난 뒤, graph에 담긴 미세먼지 값을 모두 더해주면 답을 구할 수 있습니다.

 

import sys, copy
input = sys.stdin.readline

def dust_in(x,y):
    temp = 0
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0<= nx < r and 0<= ny < c and graph[nx][ny] != -1:
            temp += (graph[nx][ny] // 5)
    return temp

def dust_out(x,y):
    temp = 0
    cnt = 0
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0<= nx < r and 0<= ny < c and graph[nx][ny] != -1:
            cnt += 1
    temp += (graph[x][y] // 5) * cnt
    return temp

def air_clean(graph,new_graph):
    # 위쪽 반시계
    graph[air-1][1] = 0
    for i in range(2, c):
        graph[air-1][i] = new_graph[air-1][i-1]

    for i in range(air-1):
        graph[i][-1] = new_graph[i+1][-1]

    for i in range(c-1):
        graph[0][i] = new_graph[0][i+1]

    for i in range(1, air-1):
        graph[i][0] = new_graph[i-1][0]

    for i in range(1, air-1):
        for j in range(1, c-1):
            graph[i][j] = new_graph[i][j]

    # 아래쪽 시계
    graph[air][1] = 0
    for i in range(2, c):
        graph[air][i] = new_graph[air][i-1]

    for i in range(air+1, r):
        graph[i][-1] = new_graph[i-1][-1]

    for i in range(c-1):
        graph[r-1][i] = new_graph[r-1][i+1]

    for i in range(air+1, r-1):
        graph[i][0] = new_graph[i+1][0]


    for i in range(air+1, r-1):
        for j in range(1, c-1):
            graph[i][j] = new_graph[i][j]


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

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

air = 0 
for i in range(r): 
    if graph[i][0] == -1:
        air = i + 1
        break

for _ in range(t):
    new_graph = copy.deepcopy(graph)
    for i in range(r):
        for j in range(c):
            if graph[i][j] != -1:
                total_dust = (dust_in(i,j) - dust_out(i,j))
                new_graph[i][j] += total_dust
    air_clean(graph,new_graph)

result = 0
for i in range(r):
    for j in range(c):
        if graph[i][j] != -1:
            result += graph[i][j]

print(result)