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

백준 17144_미세먼지 안녕!

# 조건

• 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다.
• 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다.
• 구사과는 뛰어난 코딩 실력을 이용해 각 칸 (r, c)에 있는 미세먼지의 양을 실시간으로 모니터링하는 시스템을 개발했다. (r, c)는 r행 c열을 의미한다.

• 공기청정기는 항상 1번 열에 설치되어 있고, 크기는 두 행을 차지한다.
• 공기청정기가 설치되어 있지 않은 칸에는 미세먼지가 있고, (r, c)에 있는 미세먼지의 양은 Ar,c이다.

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

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

아래는 확산의 예시

 

 

공기청정기의 순환

 

# 접근 방법

• 주어진 규칙에 따라 먼지를 확산시키고, 이동시키면 된다.
• 확신시키는 diffusion함수, 공기청정기를 이동 시키는 move_first, move_second함수를 구현해줄 것이다.
• 우선 확산시킬 때 동시에 모든 미세 먼지가 확산을 시키므로 확산된 값을 저장해줄 temp_arr을 만들어 주고 deepcopy를 통하여 원본 배열과 함께 인자로 넘겨준다.
  • 원본 배열에 값이 존재한다면 => 미세 먼지가 있다면
  • 규칙에 따라 확산 가능한 주변 칸이 있다면 임시 배열에 arr[i][j] // 5를 더해준다.
  • 4방향 탐색이 끝난 후 확산 시킨 칸도 arr[i][j] - (arr[i][j]//5) * cnt를 임시 배열에 더해준다.
  • 모든 미세먼지의 확산이 끝났다면 확산이 완료된 임시 배열을 return 해준다.
• return 받은 임시 배열과 움직이는 방향을 인자로 move함수를 실행시켜주고, 이동이 완료된 배열을 원본 배열에 다시 저장해준다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  
from copy import deepcopy  

def solve():  
    # 미세먼지 확산  
    def diffusion(temp_arr, arr):  
        for i in range(R):  
            for j in range(C):  
                if arr[i][j] and (i, j) not in air:  
                    # 현재 좌표에서 확산 시킨 칸의 개수  
                    # 확산시키는 칸의 // 5로 임시 배열에 더해주기                    
                    cnt = 0  
                    val = arr[i][j] // 5  
                    for d in range(4):  
                        ni, nj = i + di[d], j + dj[d]  
                        if 0<=ni<R and 0<=nj<C and arr[ni][nj] != -1:  
                            temp_arr[ni][nj] += val  
                            cnt += 1  
                    temp_arr[i][j] += arr[i][j] - (val * cnt)  
                if arr[i][j] == -1:  
                    temp_arr[i][j] = -1  

        return temp_arr  

    # 첫 번째 공기 청정기 => 상 우 하 좌로 돌면서 다음 좌표 복사해주기  
    def move_first(dx, dy, start, arr):  
        si, sj = start[0], start[1]  
        # 각 모서리 도착 따른 조건 분기 해주기  
        for d in range(4):  
            while 0<=si<R and 0<=sj<C:  
                if d == 0:  
                    if not si == 0:  
                        arr[si][sj] = arr[si-1][sj]  
                    else: break  
                elif d == 1:  
                    if not sj == C-1:  
                        arr[si][sj] = arr[si][sj+1]  
                    else: break  
                elif d == 2:  
                    if not si == start[0]:  
                        arr[si][sj] = arr[si+1][sj]  
                    else: break  
                elif d == 3:  
                    if not sj == 1:  
                        arr[si][sj] = arr[si][sj-1]  
                    else: break  
                si += dx[d]  
                sj += dy[d]  
        # 출발지점 -1로 다시 표시  
        arr[si][sj] = 0  
        arr[si][sj-1] = -1  
        return arr  
    # 2번째 공기청정기 => 하 우 상 좌로 순회하면서 다음 좌표의 값 복사해주기  
    def move_second(dx, dy, start, arr):  
        si, sj = start[0], start[1]  
        # 각 모서리 도착 따른 조건 분기 해주기  
        for d in range(4):  
            while 0<=si<R and 0<=sj<C:  
                if d == 0:  
                    if not si == R-1:  
                        arr[si][sj] = arr[si+1][sj]  
                    else:  
                        break  
                elif d == 1:  
                    if not sj == C-1:  
                        arr[si][sj] = arr[si][sj+1]  
                    else: break  
                elif d == 2:  
                    if not si == start[0]:  
                        arr[si][sj] = arr[si-1][sj]  
                    else: break  
                elif d == 3:  
                    if not sj == 1:  
                        arr[si][sj] = arr[si][sj-1]  
                    else: break  
                si += dx[d]  
                sj += dy[d]  
        # 출발지점 -1로 다시 표시  
        arr[si][sj] = 0  
        arr[si][sj-1] = -1  
        return arr  



    R, C, T = map(int, input().split())  
    room = [[*map(int, input().split())] for _ in range(R)]  
    air = []  
    di, dj = [-1, 1, 0, 0], [0, 0, 1, -1]  
    for i in range(R):  
        for j in range(C):  
            if room[i][j] == -1:  
                air.append((i, j))  

    temp = [[0] * C for _ in range(R)]  
    for _ in range(T):  
        # 미세먼지 확산에 원본 배열 넣고 확산시킨 확산된 배열 리턴 받기  
        diff_arr = diffusion(deepcopy(temp), room)  
        # 리턴 받은 확산된 배열 공기청정기로 먼지 이동시키고 원본 배열에 다시 저장해주기.  
        # 공기청정기 움직이는 건 시계 방향으로 해주면서 배열에 복사        
        # 위쪽 공기청정기와 아래쪽 공기청정기 움직이는 순서 인자로 넘겨주기        
        room = move_first([-1, 0, 1, 0], [0, 1, 0, -1], air[0], diff_arr) 
        room = move_second([1, 0, -1, 0], [0, 1, 0, -1], air[1], room)  

    result = 0  
    for i in room:  
        result += sum(i)  
    print(result+2)  
solve()