[백준][Python] 17144 - 미세먼지 안녕

문제 링크

17144번: 미세먼지 안녕!

---

문제 풀이 과정

T 초 후에 방에 미세먼지가 얼마나 남았는지 총합을 계산하는 문제.

• 미세먼지와 공기청정기 파트로 나눠서 생각하고 구현
• 미세먼지
  • 미세먼지는 인접한 4개(상하좌우) 방향으로 확산
  • 확산할 공간에 공기청정기가 있거나 공간의 끝이면 확산되지 않음.
  • 확산되는 양은 A(기존에 미세먼지가 있었던 칸의 양) // 5
  • 확산되면 기존 칸의 양은 A - ((A // 5) * 확산된 방향 수)
• 공기청정기
  • 1열에 2칸에 -1의 형태로 존재.
  • 상부와 하부에 따라 바람 방향이 반대로 순환(상부 : 반시계, 하부 : 시계)
  • 미세먼지는 공기청정기의 바람 방향에 따라 이동함.(바람이 닿는 곳만)
  • 순환하다가 공기청정기와 닿으면 미세먼지는 사라짐.

from sys import stdin
input = stdin.readline

# 입력을 받는 부분
R, C, T = map(int, input().rstrip().split())

# 이차원 그래프를 만드는 부분
graph = [list(map(int, input().rstrip().split())) for _ in range(R)]

# 공기청정기 위아래 행 위치
down = 0
up = 0
for i in range(R):
    if graph[i][0] == -1:
        up = i
        down = i + 1
        break

# 미세먼지를 확산시키는 함수
# 필요한 값 : 공기청정기 위치, 4 방향에 대한 값, 전체 순회하며 값 수정.
def spread_dust():
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]

    new_graph = [[0] * C for _ in range(R)]
    new_graph[up][0] = -1
    new_graph[down][0] = -1

    for i in range(R):
        for j in range(C):
            if graph[i][j] > 0:
                new_graph[i][j] += graph[i][j]
                for k in range(4):
                    nx = i + dx[k]
                    ny = j + dy[k]

                    # 확산되는 공간이 공기청정기거나 공간의 끝이면 확산 X
                    if 0 <= nx < R and 0 <= ny < C and graph[nx][ny] != -1:
                        new_graph[nx][ny] += graph[i][j] // 5
                        new_graph[i][j] -= graph[i][j] // 5
    return new_graph


# 공기청정기 바람을 이동시키는 함수
def clean():
    # 공기청정기를 진행 방향에 따라 한 줄 씩 진행
    # 반시계면 아래 => 오른쪽 => 위 => 왼쪽 순

    # 위쪽 공기청정기 작동 (반시계 방향 순환)
    for i in range(up - 1, 0, -1): # 상단에서 아래로
        graph[i][0] = graph[i - 1][0]
    for i in range(C - 1): # 왼쪽에서 오른쪽으로
        graph[0][i] = graph[0][i + 1]
    for i in range(up): # 위에서 아래로
        graph[i][C - 1] = graph[i + 1][C - 1]
    for i in range(C - 1, 1, -1): # 오른쪽에서 왼쪽으로
        graph[up][i] = graph[up][i - 1]
    graph[up][1] = 0  # 공기청정기 바로 옆은 항상 0

    # 아래쪽 공기청정기 작동 (시계 방향 순환)
    for i in range(down + 1, R - 1):  # 하단에서 위로
        graph[i][0] = graph[i + 1][0]
    for i in range(C - 1): # 왼쪽에서 오른쪽으로
        graph[R - 1][i] = graph[R - 1][i + 1]
    for i in range(R - 1, down, -1): # 아래에서 위로
        graph[i][C - 1] = graph[i - 1][C - 1]
    for i in range(C - 1, 1, -1): # 오른쪽에서 왼쪽으로
        graph[down][i] = graph[down][i - 1]
    graph[down][1] = 0  # 공기청정기 바로 옆은 항상 0



for _ in range(T):
    graph = spread_dust()
    clean()


print(sum([sum(line) for line in graph]) + 2)