[백준-파이썬] 17114:미세먼지 안녕!

문제 풀러 가기~

풀이

일단은 공기 청정기 위치를 찾았다. 항상 1번 열에 설치되어 있고, 크기는 두 행을 차지한다. 공기 청정기의 위쪽 행을 찾았다!

그리고 미세먼지가 확산되는 일, 공기 청정기가 작동할 때 일어나는 일을 함수로 만들었다.

미세먼지가 확산될 때는, 미리 어떤 곳에 미세먼지가 있고, 얼마나 있는지 파악해서 리스트에 넣은 후에,
그 리스트를 돌면서 인접한 네 방향으로 확산되게 했다. 또 그 위치의 미세먼지 양도 바꿔주었다.
사실 처음에는 미리 미세먼지의 위치, 양을 저장하지 않고 그냥 for문 두개로 미세먼지 있는 곳을 만나면 확산되게 했다. 그러면 원래는 미세먼지가 없었는데, 미세먼지 확산으로 이제 미세먼지가 있는 곳도 원래 미세먼지가 있던 곳처럼 처리된다. 미세먼지의 양도 원래 양만큼이 아니라, 늘어난 양을 기준으로 확산이 일어나고..

공기 청정기가 작동할 때 일어나는 일은 일일이 구현했다. 크게는 공기 청정기 위쪽과 아래쪽으로 나눌 수 있고, 그 안에서도 각각 오른쪽으로 가는 방향, 왼쪽으로 가는 방향, 위로 가는 방향, 아래로 가는 방향에 따라서 코드를 짰다.
공기가 들어가는 쪽부터 구현했다.

공기가 나가는 곳은 깨끗한 공기가 나가므로, 0으로 바꾸는 것도 잊으면 안된다 !

코드

import sys

input = sys.stdin.readline

MIIS = lambda: map(int, input().split())
directions = [(0, -1), (0, 1), (-1, 0), (1, 0)]

R, C, T = MIIS()
arr = [list(MIIS()) for _ in range(R)]


# 공기 청정기 위치 찾기
def find_air_cleaner():
    for i in range(R):
        if arr[i][0] == -1:
            return i


# 미세먼지 확산
def spread():
    # 미세 먼지 있는 모든 칸, 먼지 양을 미리 구해두자
    dust_zones = []
    for i in range(R):
        for j in range(C):
            if arr[i][j] > 0:
                dust_zones.append((i, j, arr[i][j]))

    # 그 곳에서 먼저 확산
    for i, j, origin_volume in dust_zones:
        spread_volume = origin_volume // 5  # 확산되는 양

        # 확산될 것이 없으면 컨티뉴
        if spread_volume == 0:
            continue
        spread_cnt = 0
        # 인접한 네 방향으로 확산
        for k in range(4):
            ni = i + directions[k][0]
            nj = j + directions[k][1]

            # 범위 내
            if ni < 0 or ni >= R:
                continue
            if nj < 0 or nj >= C:
                continue

            # 공기 청정기 아니고
            if ni == air_cleaner_i and nj == 0:
                continue
            if (ni == air_cleaner_i + 1) and nj == 0:
                continue

            arr[ni][nj] += spread_volume
            spread_cnt += 1
        # 남은 미세먼지 양
        arr[i][j] -= (spread_volume * spread_cnt)


# 공기청정기 작동
def air_cleaner():
    # 위쪽

    # 아래쪽으로
    for i in range(air_cleaner_i - 1, 0, -1):
        arr[i][0] = arr[i - 1][0]

    #  <-
    for j in range(C - 1):
        arr[0][j] = arr[0][j + 1]

    # 위로
    for i in range(air_cleaner_i):
        arr[i][C - 1] = arr[i + 1][C - 1]

    # ->
    for j in range(C - 1, 0, -1):
        arr[air_cleaner_i][j] = arr[air_cleaner_i][j - 1]
    # 공기청정기에서 나온 바람
    arr[air_cleaner_i][1] = 0

    # 아래

    # 위로
    for i in range(air_cleaner_i + 2, R - 1):
        arr[i][0] = arr[i + 1][0]

    #  <-
    for j in range(C - 1):
        arr[R - 1][j] = arr[R - 1][j + 1]

    # 아래쪽으로
    for i in range(R - 1, air_cleaner_i + 1, -1):
        arr[i][C - 1] = arr[i - 1][C - 1]

    # ->
    for j in range(C - 1, 0, -1):
        arr[air_cleaner_i + 1][j] = arr[air_cleaner_i + 1][j - 1]
    # 공기청정기에서 나온 바람
    arr[air_cleaner_i + 1][1] = 0


air_cleaner_i = find_air_cleaner()
for _ in range(T):  # T초만큼 반복
    spread()
    air_cleaner()

# 남은 먼지 양
left_dust = 0
for i in range(R):
    left_dust += sum(arr[i])
print(left_dust + 2)  # 공기 청정기

소감

구현, 시뮬레이션 문제..
나는 이런 문제는 말 그대로 그냥 어떻게 돌아가는지 파악해서 구현하면 되니까 쉽다고 생각했었다...
그런데 어려운 문제는 어려운 것 같다..
인덱스도 잘 따져야 하고, 순서나 조건도 잘 체크해야 하고..
구현 문제도 연습 해야지 !! 화이팅!!

아~ 그리고 파이파이로만 통과하고 파이썬은 시간초과가 나왔다 ㅠㅠ