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

문제

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

 

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

1초 동안 아래 적힌 일이 순서대로 일어난다.

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

다음은 확산의 예시이다.

 

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

 

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

 

공기청정기가 있는 칸으로는 확산이 일어나지 않는다.

 

공기청정기의 바람은 다음과 같은 방향으로 순환한다.

 

방의 정보가 주어졌을 때, 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

예제 출력 1

188

 

 

 

import sys
input = sys.stdin.readline

def dust_spread():
    # 모두 동시에 일어나니까 별도의 배열 생성... 
    # 기존 배열을 돌면서 먼지가 있다면 4개 방향으로 값/5한 정수를 더해주고, 옮길수있는만큼 -해주기.
    # 인접한 곳에 -1(공청기 있음)이 있거나 인덱스 밖으로 벗어나는것은 건너뛴다.
    temp = [[0] * c for _ in range(r)] # 확산되는 값을 저장할 임시 배열
    dx = [-1, 1, 0, 0] # 이동 방향 (상하좌우)
    dy = [0, 0, -1, 1]
    for i in range(r): # r * c만큼 반복
        for j in range(c):
            current = dust[i][j] # 현재 위치
            temp[i][j] += current # 현재값 임시배열에 저장
            if current != -1 and current != 0: # 현 위치가 공기청정기가 아니면서 비어있지않다면
                data = current // 5 # 확산되는 값
                for k in range(4): # 상하좌우로 확산시킴
                    nx = i + dx[k]
                    ny = j + dy[k]
                    # 이동할 곳이 인덱스 범위를 벗어나지 않고 공기청정기가 없는 곳이라면
                    if 0 <= nx < r and 0 <= ny < c and dust[nx][ny] != -1:
                        temp[nx][ny] += data # 확산
                        temp[i][j] -= data # 확산된만큼 원본에서 감소
    return temp # 확산시킨 배열을 리턴

def dust_rotate():
    # 공청기 0인덱스보다 위쪽이면 반시계(왼쪽으로 1칸씩 이동. 더 갈수 없다면 아래로...). 테두리만 움직임
    # 아래쪽이면 시계.(오른쪽으로 이동.)
    # 반시계 - 왼쪽
    for x in range(air1 - 1, 0, -1):
        dust[x][0] = dust[x - 1][0]
    # 반시계 - 위
    for y in range(c - 1):
        dust[0][y] = dust[0][y + 1]
    # 반시계 - 오른쪽
    for x in range(air1):
        dust[x][-1] = dust[x + 1][-1]
    # 반시계 - 아래
    for y in range(c - 1, 0, -1):
        dust[air1][y] = dust[air1][y - 1]

    # 시계 - 왼쪽
    for x in range(air2 + 1, r - 1):
        dust[x][0] = dust[x + 1][0]
    # 시계 - 아래
    for y in range(c - 1):
        dust[-1][y] = dust[-1][y + 1]
    # 시계 - 오른쪽
    for x in range(r - 1, air2, -1):
        dust[x][-1] = dust[x - 1][-1]
    # 시계 - 위
    for y in range(c - 1, 0, -1):
        dust[air2][y] = dust[air2][y - 1]

    # 바람이 나오는 곳은 미세먼지가 정화됨
    dust[air1][1] = 0
    dust[air2][1] = 0


r, c, t = map(int, input().split())
dust = [list(map(int, input().split())) for _ in range(r)]
for i in range(r):
    if dust[i][0] == -1:
        air1, air2 = i, i+1 # 공기청정기
        break

# 1초당 확산 > 이동.
for i in range(t):
    dust = dust_spread()
    dust_rotate()

# 총합 계산. 결과 출력.
result = 0
for i in dust:
    result += sum(i)

print(result + 2) # 공기청정기(-1 * 2)만큼 더해줌


# 미세먼지 안녕
# 공기청정기는 항상 1열에 설치됨. 2행 차지. (3.1 - 4.1)
# 미세먼지 확산 -> 공기청정기 작동.
# 확산은 모두 동시에 일어남. 미세먼지는 인접한 네 방향으로 확산됨.(동서남북)
# 인접한 방향에 공기청정기가 있거나 칸이 없다면 확산이 일어나지 않음.
# 확산되는 양은 /5한 정수. 남은 양은 기존값 - (/5한 정수 * 확산된 방향의 개수)
# 공청기 작동
# 바람이 나옴. 위쪽 공청기의 바람은 반시계방향(좌). 아래쪽은 시계방향(우).
# 바람이 불면 미세먼지가 바람의 방향대로 1칸씩 이동한다.
# 공청기 바람은 미세먼지가 없고 들어간 먼지는 모두 정화됨.
# -1은 공청기.
# t초가 지난 후 남아있는 미세먼지의 양 출력

 

 

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

17144번: 미세먼지 안녕!