[백준/Python]17144: 미세먼지 안녕!

문제

https://www.acmicpc.net/problem/17144
백준 문제집 - 0x0D강 - 시뮬레이션

 

알고리즘: 시뮬레이션

---

풀이

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

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

공기청정기가 설치된 곳은 Ar,c가 -1이고, 나머지 값은 미세먼지의 양이다. -1은 2번 위아래로 붙어져 있고, 가장 윗 행, 아랫 행과 두 칸이상 떨어져 있다.
방의 정보가 주어졌을 때, T초가 지난 후 구사과의 방에 남아있는 미세먼지의 양을 구해보자.

 

제일 중요한 정보가 스치듯이 명시되어있으니 주의해야한다.
공기청정기는 항상 1열에 위치한다.
(이걸 안읽고 삽질 좀 했다...)

 

사실 처음엔 큐를 사용했었는데 이 문제엔 적절하지 않은 시도였다.
한번 퍼진 미세먼지도 양이 충분하다면 계속 퍼질 수 있고, '동시에' 퍼져야하기 때문에 조건 체크하기가 번거롭다.

 

그리고 또 한가지... 공기청정기의 윗부분은 반시계방향, 아랫부분은 시계방향으로 순환한다.
이걸 어떻게 구현해야할지 고민했고 막상 구현해놓으니 뭔가 아닌것같아서 힘들었다...
나는 브레스를 쏘듯 동서남북 순환을 한번에 처리하려고 했는데(슬라이딩 퍼즐처럼), 컴퓨터에게도 나에게도 힘든 방법이었다.

단순한 방법이 제일 좋은 답인 경우가 꽤 있다.

 

 

먼저 입력 데이터들을 정리해야한다.
공기청정기의 위치는 불변적이므로 따로 저장해둬야 하는데, 첫번째로 발견된 -1은 윗부분, 두번째는 아랫부분이다.
어차피 공기청정기는 항상 1열(인덱스로는 0)에 위치하므로 행만 저장해두면 된다.

for i in range(R):
    line = list(map(int, input().split()))
    A.append(line)
    for j in range(C):
        if line[j] == -1:  # 항상 1열에 위치하기때문에 행만 저장
            air_cleaner.append(i)

 

1. 먼지 확산
A의 카피본을 만든 후 행렬 하나하나를 체크해야한다.
먼지 확산은 '동시다발적으로' 일어나는것이므로 원본 A를 수정해버리면 후에 먼지 계산에 영향을 주게된다.

 

만약 현재 칸에 먼지가 존재한다면 동서남북에 해당하는 좌표를 구한다.
해당 좌표가 범위 내라면 (현재 칸의 미세먼지 // 5) 만큼 퍼뜨리고 카운트를 추가한다.
모두 퍼뜨렸다면 현재 칸의 미세먼지에서 (현재 칸의 미세먼지 // 5) * 카운트횟수 만큼 제한다.
그리고 A의 카피본을 A로 업데이트한다.

 

2. 공기청정기의 순환
윗부분은 반시계방향, 아랫부분은 시계방향으로 순환한다.
돌고 돌아 공기청정기에 흡입(?)되면 사라진다.

 

공기청정기에서 바람이 나오는 부분을 0, 흡입되는 부분을 3이라 한다면 3 - 2 - 1 - 0 순으로 업데이트 해주면 된다.
그림처럼 0 - 1 - 2 - 3 순으로 해결해도 되지만 따로 temp값을 만들어둬야 하므로 번거롭다.
3 - 2 - 1 - 0 순으로 진행시 흡입부분에 위치한 칸은 아예 버리고 시작할 수 있으므로 훨씬 순조롭다.

따라서 윗부분의 순환 순서는 1) 위쪽 → 아래쪽(흡입), 2) 오른쪽 → 왼쪽, 3) 아래쪽 → 위쪽, 4) 왼쪽(청정기) → 오른쪽 이 된다.
또한 4번 진행시 청정기의 바로 옆 칸은 0으로 업데이트해줘야한다.

위에 사족에서 공기청정기의 순환을 슬라이딩 퍼즐과 같이 생각했다고 했는데, 퍼즐의 구조를 생각해보면 이 순서가 옳다. 우선 빼고 밀어내는것이다.

 

전체 코드

# 메모리: 31120KB / 시간: 1884ms
from sys import stdin


input = stdin.readline

R, C, T = map(int, input().split())
A = []

air_cleaner = []
directions = [(0, 1), (-1, 0), (0, -1), (1, 0)]

for i in range(R):
    line = list(map(int, input().split()))
    A.append(line)
    for j in range(C):
        if line[j] == -1:  # 항상 1열에 위치하기때문에 행만 저장
            air_cleaner.append(i)


def spread_dust():
    A_copy = [line[:] for line in A]

    for i in range(R):
        for j in range(C):
            if A[i][j] > 0:
                new_dust = A[i][j] // 5
                cnt = 0
                for dx, dy in directions:
                    nx, ny = i + dx, j + dy
                    if 0 <= nx < R and 0 <= ny < C and A[nx][ny] != -1:
                        A_copy[nx][ny] += new_dust
                        cnt += 1
                A_copy[i][j] -= new_dust * cnt
    return A_copy

# ⭐ 공기청정기에서 퍼져나가는 쪽이 빨아들이는 쪽부터 업데이트한다.

# 공기청정기의 윗부분
def cleaning_top():
    top = air_cleaner[0]

    # 위 -> 아래로 빨아들이기
    for i in range(top-1, 0, -1):
        A[i][0] = A[i-1][0]
    # 오른쪽 -> 왼쪽으로
    for i in range(C-1):
        A[0][i] = A[0][i+1]
    # 아래 -> 위
    for i in range(top):
        A[i][C-1] = A[i+1][C-1]
    # 왼쪽 -> 오른쪽
    for i in range(C-1, 1, -1):
        A[top][i] = A[top][i-1]
    A[top][1] = 0

# 공기청정기의 아랫부분
def cleaning_bottom():
    bottom = air_cleaner[1]

    # 아래 -> 위
    for i in range(bottom+1, R-1):
        A[i][0] = A[i+1][0]
    # 오른쪽 -> 왼쪽
    for i in range(C-1):
        A[R-1][i] = A[R-1][i+1]
    # 위 -> 아래
    for i in range(R-1, bottom, -1):
        A[i][C-1] = A[i-1][C-1]
    # 왼쪽 -> 오른쪽
    for i in range(C-1, 1, -1):
        A[bottom][i] = A[bottom][i-1]
    A[bottom][1] = 0


for _ in range(T):
    A = spread_dust()
    cleaning_top()
    cleaning_bottom()

ret = 0
for row in A:
    for col in row:
        if col > 0:
            ret += col

print(ret)

순환 구간 범위만 잘 설정하면 쉬운 문제다!