백준_17144_미세먼지 안녕!

문제

17144번: 미세먼지 안녕!

풀이

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)

알고리즘

• 구현
• 시뮬레이션