17144번. 미세먼지 안녕!

http://boj.kr/17144

17144번: 미세먼지 안녕!

 

 

 

모든 미세먼지가 '동시에' 확산한다고 해서 BFS인가 했더니만 그냥 배열 크기만큼 돌면서 시뮬레이션해주는 문제였다.

RxC을 돌며 4방향 확산->공기청정기의 순환->RxC을 돌며 4방향 확산->공기청정기의 순환

이 과정을 T만큼 반복해야 한다.

 

주의해야 할 점은 모든 미세먼지는 동시에 확산된다는 점이다.

즉, 한 번의 로테이션 동안에는 서로 영향을 줘서는 안된다.

주변으로 확산될 미세먼지를 주변에 바로 더하면 안되고 따로 저장해둔 뒤에, 한꺼번에 확산시켜야 된다는 것이다.

(r, c)에서 미세먼지가 확산되버리면 다음 반복문인 (r, c+1)의 미세먼지 양을 계산할 때 영향을 주기 때문이다. 

나는 room[R][C] = [현재 미세먼지, 다음번에 주변으로 확산될 미세먼지] 로 저장했다. 

일단 한번 RxC를 돌면서 현재 미세먼지를 전부 계산한 후에, 다시한번 처음부터 RxC를 돌면서 저장된 미세먼지를 주변으로 확산시켰다.

 

공기청정기로 인한 미세먼지의 이동은 BFS 때처럼 배열을 만들어놓고 range로 총 4번 방향을 꺾게 하는 방법,

아니면 직접 총 8번의 for문으로 구역을 나누어서 이동시키는 방법이 있다.

나는 전자의 방법으로 처음에 시도했는데 하다보니 헷갈려서 시간을 너무 오래 썼다.

보다 간단하고 디버깅도 구역별로 나눠서 가능한 후자가 더 나을 것 같다.

(코드 내에서 전자의 방법은 air_fresh_upside & air_fresh_downside 함수이고

후자의 방법은 73-83번 줄의 for문이다. 윗부분만 for문으로 했기 때문에 4줄이다.)

 

전자이든 후자이든, 중요한 것은 공기청정기에 들어온 미세먼지는 사라진다는 것인데,

이것은 바꿔말하면 공기청정기 다음 위치(문제에서 보면 col + 1 한 곳)에 0이 들어온다는 뜻이 된다.

하지만 헷갈려서 공기청정기 이전 위치를 0으로 바꾼다던가 공기청정기를 다시 -1로 돌려놓지 않는다던가 하는 일이 발생하게 된다...

항상 초록색 네모가 0이 된다고 생각하면 된다.

 

import sys


def Print(lst):
    for i in lst:
        for j in i:
            print(j[0], end=' ')
        print("")
    print("")


def air_fresh_upside(r, c):
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]

    for d in range(4):
        while True:
            if 0 <= r + dx[d] <= head_loc[0] and 0 <= c + dy[d] < C:
                if room[r+dx[d]][c+dy[d]][0] == -1:
                    room[r][c][0] = 0
                    break
                else:
                    room[r][c][0] = room[r+dx[d]][c+dy[d]][0]
                r += dx[d]
                c += dy[d]
            else:
                break
    room[head_loc[0]][head_loc[1]][0] = -1


def air_fresh_downside(r, c):
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    for d in range(4):
        while True:
            if tail_loc[0] <= r + dx[d] < R and 0 <= c + dy[d] < C:
                if room[r+dx[d]][c+dy[d]][0] == -1:
                    room[r][c][0] = 0
                    break
                else:
                    room[r][c][0] = room[r + dx[d]][c + dy[d]][0]
                r += dx[d]
                c += dy[d]
            else:
                break
    room[tail_loc[0]][tail_loc[1]][0] = -1


def solve():
    for _ in range(T):
        for r in range(R):
            for c in range(C):
                if room[r][c][0] >= 5:  # 미세먼지가 5 이상이면 확산함
                    dust_num = 0
                    for dr, dc in [[0, 1], [0, -1], [1, 0], [-1, 0]]:  # 상하좌우
                        if 0 <= r + dr < R and 0 <= c + dc < C:  # room 범위 내에서 &
                            if room[r+dr][c+dc][0] != -1:  # 공기청정기 영역이 아니라면 확산
                                dust_num += 1
                                room[r+dr][c+dc][1] += room[r][c][0] // 5
                    room[r][c][0] = room[r][c][0] - (room[r][c][0]//5) * dust_num

        # 확산된 미세먼지(room[r][c][1])를 기존 미세먼지에(room[r][c][0]) 합친다
        for r in range(R):
            for c in range(C):
                room[r][c][0] += room[r][c][1]
                room[r][c][1] = 0

        # 미세먼지의 이동 (방법 1)
        #air_fresh_upside(head_loc[0]-1, head_loc[1])
        air_fresh_downside(tail_loc[0]+1, tail_loc[1])

        # 미세먼지 이동 (방법 2)
        for i in range(0, C-1):
            room[0][i][0] = room[0][i+1][0]
        for i in range(0, head_loc[0]+1):
            room[i][C-1][0] = room[i+1][C-1][0]
        for i in range(0, C-1):
            room[head_loc[0]][C-1-i][0] = room[head_loc[0]][C-2-i][0]
        for i in range(0, head_loc[0]):
            room[head_loc[0]-i][0][0] = room[head_loc[0]-1-i][0][0]
        room[head_loc[0]][head_loc[1]+1][0] = 0
        room[head_loc[0]][head_loc[1]][0] = -1

        #Print(room)

    # sum
    ret = 0
    for r in range(R):
        for c in range(C):
            ret += room[r][c][0]
    return ret + 2


input = sys.stdin.readline
R, C, T = map(int, input().split())
room = [list(map(int, input().split())) for _ in range(R)]
head_loc, tail_loc = [], []  # 공기청정기 윗부분. 아랫부분 위치

for i in range(R):
    for j in range(C):
        if room[i][j] == -1:
            if head_loc:
                tail_loc = [i, j]
            else:
                head_loc = [i, j]
        room[i][j] = [room[i][j], 0]  # [현재 미세먼지, 다음에 확산되서 합쳐질 미세먼지]

print(solve())