[백준/파이썬] 17144번 미세먼지 안녕!

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

17144번: 미세먼지 안녕!

진짜 순수 구현문제다.. 방향벡터를 이용해야하는 정도?만 제외하면..

 

오랜만에 푸는 문제라 많이 어지러웠지만, 그래도 풀었다..!

 

문제의 해결방법은 다음과 같다

1. 미세먼지가 확산한다.

2. 공기청정기가 작동한다.

3. 위 과정을 T번 반복한다.

 

사실 2번은 정말 노가다..라고 할 수 있다. 그냥 값들을 앞으로 옮기기만 하면 되는데, for문이든 while문이든 취향껏 골라서 풀면 된다.

이제 보니 while문써서 인덱스 하나(행 또는 열 값)만을 가지고 푸는 방법이 더 깔끔할 것 같긴 하다.

 

1번이 살짝 어려울 수 있는데, 어려운 이유는 아마 다음과 같을 것 이다.

미세먼지가 확산을 하는데, 근처 칸에다가 확산된 값을 더해주면 원래 있던 값이 훼손된다 !!

 

이를 방지하기 위해, 임의의 배열을 하나 만들어서 여기에는 확산된 먼지를 적어주고, tmp에는 확산된 미세먼지의 총량을 기록해주어서

확산이 되고난 후, 확산의 기준점에 tmp 값을 빼줘서 수식을 만족시켜준다. 그리고 마지막으로 원래 배열과 임의의 배열끼리 더해서 확산을 마무리한다!

 

이 같은 방식이 가능한 이유는, 미세먼지 확산 시에 원래 있던 미세먼지 총량이 커지거나 작아지지 않기 때문이다! (숫자 계산해보면 알게 되실 겁니다)

import sys
from collections import deque
#sys.setrecursionlimit(10**6)
input = sys.stdin.readline

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

def clean():
    for i in range(first[0]-1,-1,-1): # ㅜ
        if board[i+1][0] == -1: board[i][0]=0
        else : board[i+1][0] = board[i][0]
        
    for i in range(1,c): # ㅓ
        board[0][i-1] = board[0][i]
    
    for i in range(1,first[0]+1): #ㅗ
        board[i-1][c-1] = board[i][c-1]
        
    for i in range(c-1,0,-1): # ㅏ
        if board[first[0]][i-1] == -1 : board[first[0]][i]=0
        else :board[first[0]][i] = board[first[0]][i-1]
    #------
    
    for i in range(second[0]+1,r): #ㅗ
        if board[i-1][0] == -1: board[i][0]=0
        else : board[i-1][0] = board[i][0]
        
    for i in range(1,c): #ㅓ
        board[r-1][i-1] = board[r-1][i]
    
    for i in range(r-1,second[0],-1): #ㅜ
        board[i][c-1] = board[i-1][c-1]
        
    for i in range(c-1,0,-1): #ㅏ
        if board[second[0]][i-1] == -1 : board[second[0]][i]=0
        else : board[second[0]][i] = board[second[0]][i-1]

def bfs():
    for _ in range(t):
        tmp_arr = [[0] * c for _ in range(r)]
        for x in range(r):
            for y in range(c):
                if board[x][y] > 0:
                    tmp = 0
                    for i in range(4):
                        nx = x + dx[i]
                        ny = y + dy[i]
                    
                        if nx <0 or ny <0 or nx >= r or ny >= c:
                            continue
                        if board[nx][ny] == -1: continue
                        
                        tmp_arr[nx][ny] += board[x][y] // 5
                        tmp += board[x][y] // 5
                    board[x][y] -= tmp
                    
        for i in range(r):
            for j in range(c):
                board[i][j] += tmp_arr[i][j]    
        
        clean()
        
    sum = 0
    for row in board:
        for data in row:
            if data != -1:
                sum += data
    return sum

if __name__ == "__main__":
    r,c,t = map(int,input().split())
    board = [[0]*c for _ in range(r)]

    first = [0,0]
    second = [0,0]
    
    for i in range(r):
        board[i] = list(map(int,input().split()))
        for j in range(len(board[i])):
            if board[i][j] == -1:
                if first==[0,0]:
                    first = [i,j]
                else: second = [i,j]
            
    print(bfs())