[Python] [BOJ] 미세먼지 안녕!(17144)

💡 문제 해결

1. 공기청정기 위치의 좌표를 찾아 저장
2. 먼지의 확산이 먼저 일어나므로 diffusion함수 실행
3. 확산되는 먼지를 저장할 배열 생성
4. 확산된 먼지와 탐색이 완료된 배열의 정보로 새롭게 생성한 리스트 내용 갱신
5. 본래의 리스트에 확산된 먼지를 저장했던 리스트 내용을 복제
6. 공기청정기 작동 함수인 aircleaner 실행
7. 공기청정기의 윗부분과 아랫부분의 먼지를 각각 방향에 맞게 이동
8. 전체 배열을 탐색하며 남아있는 먼지를 합산하여 출력

📌 코드가 다소 길어져버렸지만 내용은 단순
📌 '모두 동시에 일어난다' == 새로운 배열을 생성하여 결과를 저장해준다
📌 윗부분과 아랫부분의 공기청정기를 작동시킬때, 마지막 방향에 상한선과 하한선이 존재

🧾 문제 설명

미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 
공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 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. 공기청정기가 작동한다.
- 공기청정기에서는 바람이 나온다.
- 위쪽 공기청정기의 바람은 반시계방향으로 순환하고, 아래쪽 공기청정기의 바람은 시계방향으로 순환한다.
- 바람이 불면 미세먼지가 바람의 방향대로 모두 한 칸씩 이동한다.
- 공기청정기에서 부는 바람은 미세먼지가 없는 바람이고, 공기청정기로 들어간 미세먼지는 모두 정화된다.

방의 정보가 주어졌을 때, T초가 지난 후 구사과의 방에 남아있는 미세먼지의 양을 구해보자.

문제보기

🖨 입출력

📝 풀이

import sys

input = sys.stdin.readline
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]

def diffusion(R, C):
    dust_arr = [[0] * C for _ in range(R)]
    
    for i in range(R):
        for j in range(C):
            if arr[i][j] > 0:
                cnt = 0
                for k in range(4):
                    nx = i + dx[k]
                    ny = j + dy[k]
                    if 0 <= nx < R and 0 <= ny < C:
                        if arr[nx][ny] != -1:
                            dust_arr[nx][ny] += arr[i][j] // 5
                            cnt += 1
                if cnt:
                    dust_arr[i][j] += arr[i][j] - (arr[i][j] // 5) * cnt

    for i in range(R):
        for j in range(C):
            if dust_arr[i][j] > 0:
                arr[i][j] = dust_arr[i][j]
    return


def aircleaner(R, C, air_cleaner_point):
    top, bottom = air_cleaner_point
    down(R, *left(*up(*right(C, 0, *top))), top[0])
    up(*left(*down(R, *right(C, 0, *bottom))), bottom[0])
    return


def up(pre_dust, x, y, *limit_top):
    x -= 1
    while x > limit_top[0] if limit_top else x >= 0:
        current_dust = arr[x][y]
        arr[x][y] = pre_dust
        pre_dust = current_dust
        x -= 1
    return pre_dust, x + 1, y


def down(R, pre_dust, x, y, *limit_bottom):
    x += 1
    while x < limit_bottom[0] if limit_bottom else x < R:
        current_dust = arr[x][y]
        arr[x][y] = pre_dust
        pre_dust = current_dust
        x += 1
    return pre_dust, x - 1, y


def left(pre_dust, x, y):
    y -= 1
    while y >= 0:
        current_dust = arr[x][y]
        arr[x][y] = pre_dust
        pre_dust = current_dust
        y -= 1
    return pre_dust, x, y + 1


def right(C, pre_dust, x, y):
    y += 1
    while y < C:
        current_dust = arr[x][y]
        arr[x][y] = pre_dust
        pre_dust = current_dust
        y += 1
    return pre_dust, x, y - 1



R, C, T = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(R)]

air_cleaner_point = []
for i in range(R):
    for j in range(C):
        if arr[i][j] == -1:
            air_cleaner_point.append((i, j))

for _ in range(T):
    diffusion(R, C)
    aircleaner(R, C, air_cleaner_point)

answer = 0
for i in range(R):
    for j in range(C):
        if arr[i][j] > 0:
            answer += arr[i][j]

print(answer)

• 출처: BAEKJOON Online Judge
• 링크: https://www.acmicpc.net/problem/17144