[BOJ][🟡4][백준#17144] 미세먼지 안녕!

문제 출처

BAEKJOON Online Judge #17144

문제

미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사과는 뛰어난 코딩 실력을 이용해 각 칸 (r, c)에 있는 미세먼지의 양을 실시간으로 모니터링하는 시스템을 개발했다. (r, c)는 r행 c열을 의미한다.

공기청정기는 항상 1번 열에 설치되어 있고, 크기는 두 행을 차지한다. 공기청정기가 설치되어 있지 않은 칸에는 미세먼지가 있고, (r, c)에 있는 미세먼지의 양은 Ar,c이다. 1초 동안 아래 적힌 일이 순서대로 일어난다.

미세먼지가 확산된다. 확산은 미세먼지가 있는 모든 칸에서 동시에 일어난다.

(r, c)에 있는 미세먼지는 인접한 네 방향으로 확산된다. 인접한 방향에 공기청정기가 있거나, 칸이 없으면 그 방향으로는 확산이 일어나지 않는다. 확산되는 양은 Ar,c/5이고 소수점은 버린다. (r, c)에 남은 미세먼지의 양은 Ar,c - (Ar,c/5)×(확산된 방향의 개수) 이다.

공기청정기가 작동한다.

공기청정기에서는 바람이 나온다. 위쪽 공기청정기의 바람은 반시계방향으로 순환하고, 아래쪽 공기청정기의 바람은 시계방향으로 순환한다. 바람이 불면 미세먼지가 바람의 방향대로 모두 한 칸씩 이동한다. 공기청정기에서 부는 바람은 미세먼지가 없는 바람이고, 공기청정기로 들어간 미세먼지는 모두 정화된다.

다음은 확산의 예시이다.

왼쪽과 오른쪽에 칸이 없기 때문에, 두 방향으로만 확산이 일어났다.

인접한 네 방향으로 모두 확산이 일어난다.

공기청정기가 있는 칸으로는 확산이 일어나지 않는다. 공기청정기의 바람은 다음과 같은 방향으로 순환한다.

방의 정보가 주어졌을 때, T초가 지난 후 구사과의 방에 남아있는 미세먼지의 양을 구해보자.

입력

첫째 줄에 R, C, T (6 ≤ R, C ≤ 50, 1 ≤ T ≤ 1,000) 가 주어진다. 둘째 줄부터 R개의 줄에 Ar,c (-1 ≤ Ar,c ≤ 1,000)가 주어진다. 공기청정기가 설치된 곳은 Ar,c가 -1이고, 나머지 값은 미세먼지의 양이다. -1은 2번 위아래로 붙어져 있고, 가장 윗 행, 아랫 행과 두 칸이상 떨어져 있다.

출력

첫째 줄에 T초가 지난 후 구사과 방에 남아있는 미세먼지의 양을 출력한다.

예제

예제 1

입력

7 8 1
0 0 0 0 0 0 0 9
0 0 0 0 3 0 0 8
-1 0 5 0 0 0 22 0
-1 8 0 0 0 0 0 0
0 0 0 0 0 10 43 0
0 0 5 0 15 0 0 0
0 0 40 0 0 0 20 0

출력

188

예제 2

입력

7 8 2
0 0 0 0 0 0 0 9
0 0 0 0 3 0 0 8
-1 0 5 0 0 0 22 0
-1 8 0 0 0 0 0 0
0 0 0 0 0 10 43 0
0 0 5 0 15 0 0 0
0 0 40 0 0 0 20 0

출력

188

예제 3

입력

7 8 3
0 0 0 0 0 0 0 9
0 0 0 0 3 0 0 8
-1 0 5 0 0 0 22 0
-1 8 0 0 0 0 0 0
0 0 0 0 0 10 43 0
0 0 5 0 15 0 0 0
0 0 40 0 0 0 20 0

출력

186

예제 4

입력

7 8 4
0 0 0 0 0 0 0 9
0 0 0 0 3 0 0 8
-1 0 5 0 0 0 22 0
-1 8 0 0 0 0 0 0
0 0 0 0 0 10 43 0
0 0 5 0 15 0 0 0
0 0 40 0 0 0 20 0

출력

178

예제 5

입력

7 8 5
0 0 0 0 0 0 0 9
0 0 0 0 3 0 0 8
-1 0 5 0 0 0 22 0
-1 8 0 0 0 0 0 0
0 0 0 0 0 10 43 0
0 0 5 0 15 0 0 0
0 0 40 0 0 0 20 0

출력

172

예제 6

입력

7 8 20
0 0 0 0 0 0 0 9
0 0 0 0 3 0 0 8
-1 0 5 0 0 0 22 0
-1 8 0 0 0 0 0 0
0 0 0 0 0 10 43 0
0 0 5 0 15 0 0 0
0 0 40 0 0 0 20 0

출력

71

예제 7

입력

7 8 30
0 0 0 0 0 0 0 9
0 0 0 0 3 0 0 8
-1 0 5 0 0 0 22 0
-1 8 0 0 0 0 0 0
0 0 0 0 0 10 43 0
0 0 5 0 15 0 0 0
0 0 40 0 0 0 20 0

출력

52

예제 8

입력

7 8 50
0 0 0 0 0 0 0 9
0 0 0 0 3 0 0 8
-1 0 5 0 0 0 22 0
-1 8 0 0 0 0 0 0
0 0 0 0 0 10 43 0
0 0 5 0 15 0 0 0
0 0 40 0 0 0 20 0

출력

46

My Sol

import sys
input = sys.stdin.readline


def diffusionMain():
    global I, J, AU, AD
    global mat
    matNew = [[0]*J for _ in range(I)]
    didj = [(-1,0),(1,0),(0,-1),(0,1)]
    for i in range(I):
        for j in range(J):
            matNew[i][j] += mat[i][j]
            if matNew[i][j] > 4:
                v = mat[i][j] // 5
                for di, dj in didj:
                    if 0<=i+di<I and 0<=j+dj<J:
                        if mat[i+di][j+dj] > -1:
                            matNew[i+di][j+dj] += v
                            matNew[i][j] -= v

    return matNew


def cleanAirUp():
    global I, J, AU, AD
    global mat, ni, nj

    ni, nj = AU - 1, 0
    while ni-1 >= 0:
        mat[ni][0] = mat[ni-1][0]
        ni -= 1

    mat[0][0:-1] = mat[0][1:]

    ni = 0
    while ni+1 <= AU:
        mat[ni][J-1] = mat[ni+1][J-1]
        ni += 1

    mat[AU][2:] = mat[AU][1:-1]

    mat[AU][1] = 0


def cleanAirDown():
    global I, J, AU, AD
    global mat, ni, nj

    ni, nj = AD+1, 0
    while ni+1 <= I-1:
        mat[ni][0] = mat[ni+1][0]
        ni += 1

    mat[I-1][0:-1] = mat[I-1][1:]

    ni = I-1
    while ni-1 >= AD:
        mat[ni][J-1] = mat[ni-1][J-1]
        ni -= 1

    mat[AD][2:] = mat[AD][1:-1]

    mat[AD][1] = 0


I, J, T = map(int, input().split())
mat = [list(map(int, input().split())) for _ in range(I)]

for i in range(I):
    if mat[i][0]==-1:
        AU, AD = i, i+1
        break

t = 0
while t < T:
    # 확산
    mat = diffusionMain()

    # 공기청정기 작동
    cleanAirUp()
    cleanAirDown()

    # t 증가
    t += 1

# 0 이상인 수를 세서 출력
ret = 0
for i in range(I):
    for j in range(J):
        if mat[i][j] > 0:
            ret += mat[i][j]
print(ret)

확산, 위 구역의 회전, 아래 구역의 회전을 각각 함수로 정의하여 t의 증가에 따라 한 번씩 호출하여 mat을 수정하도록 하였다.

확산 : diffusionMain()

2차원 배열과 델타를 활용하면 어느 정도 쉽게 해결할 수 있는 부분이었다. 함수 내부에서는 matNew라는 2차원 배열을 만드는데, 확산된 각 영역의 값들을 더하는 별도의 2차원 배열이다.

먼저 입력으로 받은 mat 2차원 배열을 완전 탐색으로 조회하여, 각 행과 열 좌표마다 기존 mat의 mat[i][j]를 matNew[i][j]에 더하고, 이 값이 4보다 크다면 확산이 가능하므로 5로 나눈 몫 v를 별도로 지정하여, 상하좌우에 확산할 수 있는 공간인지를 판단해 확산시킨다.

상하좌우는 델타를 사용하였으며, 일반적으로 델타에서 사용하는 범위 제한의 조건과 더불어 공기청정기의 조건인 음수가 아니라면 해당 좌표에 v를 더해주고, 확산 모체인 matNew[i][j]는 v를 빼준다.

이렇게 확산 전 2차원 배열인 mat의 각 칸의 값을 모두 조회하여 matNew를 완성하면 이를 반환한다. 함수 외부에서는 이 반환값을 새로운 mat 2차원 배열로 지정한다.

정화 : clearAirUp/Down()

재귀를 사용할까 했지만, 반복을 사용하는 것이 보다 가시적으로나 작성하기에 좋을 것 같아서 반복과 slicing을 사용하였다. 공기청정기로 들어가는 부분을 시작점으로 4개의 변을 모두 한 칸씩 당겨주는 것이다.

아날로그식이지만 가장 직관적인 것 같아서 활용했고, clearAirUp과 Down의 함수 모습이 비슷하지만 참조하는 값과 범위가 달라서 아예 함수를 따로 지정하는 것이 편할 것 같아 다소 중복되지만 2개로 나누었다.

while 반복문

T에 도달하기까지 1씩 증가하는 t를 따로 만들어 t가 T가 될 때까지 확산/정화의 함수 호출을 한 번씩 한다.

결과 도출

결과는 mat에 대하여 mat[i][j]가 0 이상이라면 미세먼지가 있는 것이므로 이를 합계 변수에 더해주며 완전탐색을 마치면 되겠다.

결과

맞았습니다!!

모범답안

출처

# empty