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

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

17144번: 미세먼지 안녕!

---

1. 접근 방식

• 구현 방식의 문제임을 파악하자

문제가 주절주절 길다. 지문이 이렇게 긴 이유는, 문제를 해결하기 위한 여러 조건들을 제시하기 때문이다. 그럼 문제를 꼼꼼히 읽으면서 주어진 조건대로 구현하기만 하면 된다.

 

 

• 미세먼지 확산을 구현할 때, 확산된 양 ⌊Ar,c/5⌋을 담은 배열 amount와 변경된 결과를 담을 배열 updated를 추가로 생성하자

한 번 확산이 완료되면 기존 (r, c)의 미세먼지 양은 다른 칸들로부터 영향도 받고, 자신이 얼마나 다른 칸에 미세먼지를 나눠줬는지에 따라 달라진다. 즉, 반복문을 돌면서 한 번에 (r, c) 값을 설정할 수가 없다. 다른 칸들에게서 받아오는 미세 먼지 양을 다 계산해야 하고, 또 다른 칸에게 나눠줄 자신의 ⌊Ar,c/5⌋ 값도 달라지기 때문이다.

따라서  확산된 양 ⌊Ar,c/5⌋을 담은 배열 amount과 updated 배열을 추가로 사용했다. board를 순회하면서 (r, c)가 주변에서 받는 미세 먼지 양과 자신이 미세 먼지를 나눠주고 남은 양을 계산하여 updated[r][c]에 반영한다. 이때 board 배열의 값은 변경되지 않기 때문에 이미 진행된 확산 결과에 영향을 받지 않는다.

 

 

• 시계/반시계 방향 순환은 상, 하, 좌, 우 4가지 갈래로 나눠 생각하자

위 그림에서 빨강, 주황, 파랑, 초록으로 갈래를 나눈 것처럼 인덱싱을 활용하여 상, 하, 좌, 우로 나눠 처리하는 편이 간단하다. 위 그림에서 검은색 동그라미 영역의 값은 0으로 초기화된다. 공기청정기에 의해 미세 먼지가 있었어도 날라가버리기 때문이다.

 

 

 

2. 정답 코드

import sys

input = sys.stdin.readline


def diffuse():
    directions = [(1, 0), (-1, 0), (0, -1), (0, 1)]

    amount = [[board[i][j] // 5 for j in range(C)] for i in range(R)]
    updated = [[0] * C for _ in range(R)]

    filter = []
    for i in range(R):
        for j in range(C):
            if board[i][j] == -1:
                filter.append(i)
                updated[i][j] = -1
                continue

            count = 4
            added = 0
            for d in directions:
                x, y = i + d[0], j + d[1]

                if x < 0 or x >= R or y < 0 or y >= C or board[x][y] == -1:
                    count -= 1
                else:
                    added += amount[x][y]

            updated[i][j] = board[i][j] - (amount[i][j] * count) + added

    return filter[0], filter[1], updated


def activate(filter_x, filter_y):
    # 시계 방향 순환
    for r in range(filter_x - 1, 0, -1):
        board[r][0] = board[r - 1][0]
    for c in range(C - 1):
        board[0][c] = board[0][c + 1]
    for r in range(filter_x):
        board[r][-1] = board[r + 1][-1]
    for c in range(C - 1, 0, -1):
        board[filter_x][c] = board[filter_x][c - 1]
    board[filter_x][1] = 0

    # 반시계 방향 순환
    for r in range(filter_y + 1, R - 1):
        board[r][0] = board[r + 1][0]
    for c in range(C - 1):
        board[-1][c] = board[-1][c + 1]
    for r in range(R - 1, filter_y, - 1):
        board[r][-1] = board[r - 1][-1]
    for c in range(C - 1, 0, -1):
        board[filter_y][c] = board[filter_y][c - 1]
    board[filter_y][1] = 0


def sum_dust():
    result = 0
    for row in board:
        result += sum(row)
    return result + 2  # 공기청정기 때문에 -2 되기 때문


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

for _ in range(T):
    x, y, board = diffuse()
    activate(x, y)

print(sum_dust())