[Baekjoon] 17144번: 미세먼지 안녕! (구현 Gold4) - Python

1. 문제

---

미세먼지 안녕!

2. 풀이

---

코드

import sys

input_func = sys.stdin.readline

r, c, t = map(int, input_func().split())
room = [list(map(int, input_func().split())) for _ in range(r)]
air_cleaner = []
total_dust = 0

for i in range(r):
    for j in range(c):
        if room[i][j] == -1:
            air_cleaner.append((i, j, 0))


def spread_dust():
    q = []
    for i in range(r):
        for j in range(c):
            if room[i][j] != 0 and room[i][j] != -1:
                q.append((i, j, room[i][j]))

    while q:
        cx, cy, dust = q.pop(0)
        count = 0
        spread_amount = dust // 5
        for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            nx, ny = cx + dx, cy + dy
            if 0 <= nx < r and 0 <= ny < c and room[nx][ny] != -1:
                room[nx][ny] += spread_amount
                count += 1
        room[cx][cy] -= spread_amount * count


def clean_air_top(x, y, dust):
    dx = [0, -1, 0, 1]
    dy = [1, 0, -1, 0]

    direction = 0
    cx, cy = x, y
    while True:
        nx, ny = cx + dx[direction], cy + dy[direction]
        if 0 <= nx < r and 0 <= ny < c:
            if room[nx][ny] == -1:
                break
            else:
                room[nx][ny], dust = dust, room[nx][ny]
            cx, cy = nx, ny
        else:
            direction += 1


def clean_air_bottom(x, y, dust):
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]

    direction = 0
    cx, cy = x, y
    while True:
        nx, ny = cx + dx[direction], cy + dy[direction]
        if 0 <= nx < r and 0 <= ny < c:
            if room[nx][ny] == -1:
                break
            else:
                room[nx][ny], dust = dust, room[nx][ny]
            cx, cy = nx, ny
        else:
            direction += 1


for _ in range(t):
    spread_dust()
    for i in range(r):
        print(room[i])
    clean_air_top(air_cleaner[0][0], air_cleaner[0][1], air_cleaner[0][2])
    clean_air_bottom(air_cleaner[1][0], air_cleaner[1][1], air_cleaner[1][2])

for i in range(r):
    for j in range(c):
        if room[i][j] != -1:
            total_dust += room[i][j]

print(total_dust)

입력 및 출력

7 8 1
0 0 0 0 0 0 0 9
0 0 0 0 3 0 0 8
-1 0 5 0 0 0 22 0
-1 8 0 0 0 0 0 0
0 0 0 0 0 10 43 0
0 0 5 0 15 0 0 0
0 0 40 0 0 0 20 0

>> 188

3. 로직

---

1. r, c, t 변수에 각각 방의 행(row), 열(column), 시간(t) 값을 저장한다.

2. room이라는 2차원 리스트를 생성하고, 입력을 받아 각 셀의 미세먼지 양을 저장한다.

3. 공기청정기 위치를 찾아 air_cleaner 리스트에 저장합니다. 공기청정기는 -1 값으로 표시되어 있다.

4. spread_dust() 함수를 정의한다. 이 함수는 미세먼지의 확산을 처리한다.

• q라는 큐를 생성하고, room을 순회하며 미세먼지가 있는 셀을 q에 추가한다.
• q에서 하나씩 미세먼지가 있는 셀을 꺼내면서, 주변 셀에 미세먼지를 확산시킨다.
• 주변 셀은 상하좌우 네 방향입니다. 범위를 벗어나지 않고 공기청정기가 없는 셀에만 미세먼지를 확산시킨다.
• 확산되는 양은 해당 셀의 미세먼지 양을 주변 셀의 개수로 나눈 값이다.
• 확산된 미세먼지 양은 주변 셀에 누적된다.

5. clean_air_top() 함수와 clean_air_bottom() 함수는 공기청정기의 작동을 처리한다.

• clean_air_top() 함수는 상단 공기청정기의 작동을 담당한다. 공기청정기 바로 위의 셀부터 시작하여 시계방향으로 회전하며 미세먼지를 이동시킨다.
• clean_air_bottom() 함수는 하단 공기청정기의 작동을 담당한다. 공기청정기 바로 아래 셀부터 시작하여 반시계방향으로 회전하며 미세먼지를 이동시킨다.
• 각 셀의 미세먼지는 이동된 이전 셀의 미세먼지로 갱신된다.

6. t번 만큼 시간에 따른 미세먼지 확산과 공기청정기 작동을 반복한다.

7. 상단 공기청정기와 하단 공기청정기에 대해 clean_air_top() 함수와 clean_air_bottom() 함수를 호출하여 미세먼지를 이동시킨다.

8. 모든 시간이 경과한 후, 방의 미세먼지 양을 계산하여 total_dust 변수에 누적합한다.

9. 최종적으로 total_dust 값을 출력한다.