[BOJ]17144. 미세먼지 안녕!

문제

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

 

사용 알고리즘

구현, 시뮬레이션

 

풀이

고려사항

1. 먼지 확산 - 확산하는 곳이 공기청정기인지, 범위를 넘어가는 곳이 아닌지

2. 공기 청정 - 방향전환, 먼지 이동 시 갱신 된 값과 이전 값 구분

 

후기

1. 이 문제에서 어려운 점은 공기 청정 값 갱신이였다.

아래 코드는 새로운 배열을 생성한 후 값을 옮기는 방식을 채택했다.

하지만 공기 청정하는 라인의 값은 갱신되지만, 

그 외의 원래 가지고 있어야하는 값이 0으로 나와 사용할 수 없었다.

이러한 방식을 사용하려면 새로운 배열을 0이 아닌 원래 배열에서 deepcopy하여 사용해야 한다.

# 잘못된 공기청정 로직

def refresh(room):

    after_room = [[0] * C for _ in range(R)]

    # 가로 확산
    for i in range(1, C):
        after_room[0][i - 1] = room[0][i]
        after_room[air_purifier][i] = room[air_purifier][i - 1]
        after_room[air_purifier + 1][i] = room[air_purifier + 1][i - 1]
        after_room[R - 1][i - 1] = room[R - 1][i]

    # 세로 확산
    for j in range(air_purifier):
        after_room[j + 1][0] = room[j][0]
        after_room[j][C - 1] = room[j + 1][C - 1]
    for k in range(air_purifier + 1, R - 1):
        after_room[k][0] = room[k + 1][0]
        after_room[k + 1][C - 1] = room[k][C - 1]
    return after_room

 

2. 위의 방식은 끼워맞춘 느낌이 강하고 범위를 고려하기 어려워

didj를 활용한 방향 전환방식으로 변환하여 코드를 수정했다.

이때, 고려해야 할 점은

1) 원래 자리인 공기청정 자리로 돌아온 경우 값을 갱신하는 것이 아니라

끝임을 인지하고 루프를 나와야한다.

2) 또한, 벽을 만났을 때 방향전환 후 값을 변경하지 않고 넘어가야한다.

3) 방향전환 후 값 변경을 시도하면 IndexError(Out of Range)가 발생한다.

4) 마지막으로, 값 변경 후 현재 위치를 변경해주어야 한다.(ci, cj = ni, nj)

 

 

코드

import sys
input = sys.stdin.readline

didj = [[0, 1], [-1, 0], [0, -1], [1, 0]]


def diffusion(room):

    after_room = [[0] * C for _ in range(R)]
    for i in range(R):
        for j in range(C):
            # 공기청정기
            if room[i][j] == -1:
                after_room[i][j] = -1

            # 미세먼지
            elif room[i][j] != 0:
                diffusion_air = room[i][j] // 5
                diffusion_cnt = 0

                for di, dj in didj:
                    ni, nj = i + di, j + dj

                    if 0 <= ni < R and 0 <= nj < C and room[ni][nj] != -1:
                        after_room[ni][nj] += diffusion_air
                        diffusion_cnt += 1

                after_room[i][j] += room[i][j] - (diffusion_air * diffusion_cnt)

    return after_room


def refresh(room):
    # 시계 반대방향 회전
    lo, temp = 0, 0
    ci, cj = air_purifiers[0], 0

    while True:
        ni, nj = ci + didj[lo][0], cj + didj[lo][1]

        # 공기청정기로 돌아온 경우
        if ni == air_purifiers[0] and nj == 0:
            break

        # 방향회전 필요한 경우
        if ni == R or nj == C or ni == -1 or nj == -1:
            lo = (lo + 1) % 4
            continue

        # 값 변경
        room[ni][nj], temp = temp, room[ni][nj]
        ci, cj = ni, nj

    # 시계 방향 회전
    lo, temp = 0, 0
    ci, cj = air_purifiers[1], 0

    while True:
        ni, nj = ci + didj[lo][0], cj + didj[lo][1]

        # 공기청정기로 돌아온 경우
        if ni == air_purifiers[1] and nj == 0:
            break

        # 방향회전 필요한 경우
        if ni == R or nj == C or ni == -1 or nj == -1:
            lo = (lo - 1) % 4
            continue

        # 값 변경
        room[ni][nj], temp = temp, room[ni][nj]
        ci, cj = ni, nj

    return room


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

air_purifiers = [i for i in range(R) if room[i][0] == -1]

for _ in range(T):
    room = refresh(diffusion(room))

dust = 2
for i in range(R):
    dust += sum(room[i])
print(dust)

 

결과