[백준] 미세먼지 안녕!

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

17144번: 미세먼지 안녕!

구현 문제입니다.

 

우선 문제부터 간단하게 요약하면, 방에 미세먼지와 공기 청정기가 있고, 매 1초마다 두가지 과정이 진행됩니다.

1. 미세먼지의 확산

2. 공기청정기로 인한 공기 정화와 순환

이러한 과정이 T 초간 일어난 후 방안의 전체 미세먼지의 수를 출력해야 하는 문제입니다. 

 

<Solution>

특별한 알고리즘이 사용되지 않고, 말 그대로 1,2의 과정을 정확하게 구현하면 됩니다. 

for loop 내부에 step1, step2과정을 넣어 T초 만큼 진행 될 수 있게 구현하였습니다.

 

실제 구현은 아래와 같습니다.

import sys
import copy
dir_r = [-1,1,0,0]
dir_c = [0,0,1,-1]
R, C, T = list(map(int,sys.stdin.readline().rstrip().split()))

array = [list(map(int, sys.stdin.readline().rstrip().split())) for _ in range(R)]

for _ in range(T):
    # step 1
    new_array = [[0 for _ in range(C)] for _ in range(R)]

    for r in range(R):
        for c in range(C):
            if array[r][c] >0:
                # spread
                dust = array[r][c]
                cnt = 0
                for i in range(4):
                    new_r = r+dir_r[i]
                    new_c = c+dir_c[i]
                    
                    if 0<=new_r<R and 0<=new_c<C: # not out of range
                        if array[new_r][new_c] == -1:
                            continue
                        new_array[new_r][new_c] += dust//5
                        cnt+=1
                array[r][c] -= dust//5 * cnt


    cleaner = []
    for r in range(R):
        for c in range(C):
            if array[r][c] == -1:
                cleaner.append(r)
                continue
            array[r][c] += new_array[r][c]
    
    # print("after step1")        
    # for e in array:
    #     print(e)
    # print("-------------------------------------")
    
    # step 2
    new_array = copy.deepcopy(array)
    # up rotate
    r = cleaner[0]
    for i in range(1,r+1):
        new_array[i][0] = array[i-1][0]
        new_array[i-1][C-1] = array[i][C-1]
    new_array[0] = array[0][1:] + [array[1][C-1]]
    new_array[r] = [-1,0] + array[r][1:-1]
    # down rotate
    r = cleaner[1]
    for i in range(r+1,R-1):
        new_array[i][0] = array[i+1][0]
        new_array[i][C-1] = array[i-1][C-1]
    new_array[R-1] = array[R-1][1:] + [array[R-2][C-1]]
    new_array[r] = [-1,0] + array[r][1:-1]
    # print("after step2")        
    # for e in new_array:
    #     print(e)
    # print("-------------------------------------")
    
    array = new_array
print(sum(list(map(sum,new_array)))+2)