코딩테스트/python

백준_17144_미세먼지 안녕!

zyin 2020. 8. 29. 20:00

문제

 

17144번: 미세먼지 안녕!

미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사

www.acmicpc.net

풀이

1. 미세먼지의 확산 : 함수 diffusion

"확산은 미세먼지가 있는 모든 칸에서 동시에 일어난다."라고 명시하고 있기 때문에, 확산되는 먼지의 양은 '변화가 있기 전의 먼지/5'로 계산하여야 한다. 

BOARD   NEW_BOARD
10 9   10 9
0 0   0 0

[초기값]

BOARD   NEW_BOARD
10-10/5-10/5
= 6		 9+10/5
= 11		   10 9
0+10/5
= 2		 0   0 0

[(0, 0) 미세먼지 10의 확산]

BOARD   NEW_BOARD
6+9/5
=7		 11-9/5
=10		   10 9
2 0+9/5
=1		   0 0

[(0, 1) 미세먼지 9의 확산]

 

2. 공기청정기의 작동 : 함수 rotationClockwise, 함수 rotationCounterclockwise

확산되는 동안에는 먼지의 총량이 변하지 않는다.

공기 청정기가 작동하면, 공기청정기 바로 위와 바로 아래 칸에 있는 먼지가 사라지므로, 매 주기마다 먼지 값을 더해 줄 필요 없이 사라지는 먼지 dust를 전체 먼지의 양 dust_sum에서 빼주면 된다.

공기청정기 작동 이전   공기청정기 작동 이후
6 5 4   5 4 3
7(dust)   3   6   2
-1 1 2   -1 0 1
-1 1 2   -1 0 1
7(dust)   3   6   2
6 5 4   5 4 3

코드

def diffusion(board) :
    new_board = [[board[i][j] for j in range(C)] for i in range(R)]
    for i in range(R) :
        for j in range(C) :
            if board[i][j]>=5 :
                d = int(new_board[i][j]/5) # 확산 되는 먼지의 양

                if board[i-1][j]!=-1 and i-1>=0 : # 아래
                    board[i-1][j] += d
                    board[i][j] -= d

                if board[(i+1)%R][j]!=-1 and i+1<R : # 위
                    board[i+1][j] += d
                    board[i][j] -= d

                if board[i][j-1]!=-1 and j-1>=0 : # 왼쪽
                    board[i][j-1] += d
                    board[i][j] -= d

                if board[i][(j+1)%C]!=-1 and j+1<C : #오른쪽
                    board[i][j+1] += d
                    board[i][j] -= d

def rotationClockwise() :
    dust, i, j = 0, r1, 0
    while j<C-1 :   #-->
        j += 1
        dust, board[i][j] = board[i][j], dust
    while i!=0:     # ↑
        i -= 1
        dust, board[i][j] = board[i][j], dust
    while j!=0 :    # <--
        j-=1
        dust, board[i][j] = board[i][j], dust
    while i!=r1-1 : # ↓
        i += 1
        dust, board[i][j] = board[i][j], dust
    return dust # 사라지는 먼지

def rotationCounterclockwise() :
    dust, i, j = 0, r2, 0
    while j<C-1 :   #-->
        j += 1
        dust, board[i][j] = board[i][j], dust
    while i!= R-1 : # ↓
        i += 1
        dust, board[i][j] = board[i][j], dust
    while j!=0 :    # <--
        j-=1
        dust, board[i][j] = board[i][j], dust
    while i!=r2+1 : # ↑
        i -= 1
        dust, board[i][j] = board[i][j], dust
    return dust # 사라지는 먼지

from sys import stdin
R, C, T = map(int, input().split())
board = [list(map(int, stdin.readline().rstrip("\n").split())) for i in range(R)]

dust_sum = 2 # 먼지 총량
robot = list()
for i in range(R) :
    if board[i][0]==-1 :robot.append(i) # 공기 청정기 위치 저장
    dust_sum += sum(board[i])
r1, r2 = robot

for t in range(T) :
    diffusion(board) # 확산
    dust_sum -= rotationClockwise() # 시계 회전
    dust_sum -= rotationCounterclockwise() # 반시계 회전
print(dust_sum)

알고리즘