STUDY/Algorithm

[백준] 17144 미세먼지 안녕! python

sinawi95 2021. 5. 18. 02:11
728x90

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

 

17144번: 미세먼지 안녕!

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

www.acmicpc.net

import sys; input = sys.stdin.readline
R, C, T = map(int, input().split())
room = []
fresher = []
for i in range(R):
    tmp = list(map(int, input().split()))
    room.append(tmp)
    if not fresher:
        for j in range(C):
            if tmp[j] == -1:
                fresher.append((i, j))
                fresher.append((i + 1,j))

while T > 0:
    T -= 1
    def spread(room):
        delta = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        room_tmp = [[0] * C for _ in range(R)]
        # room_tmp[fresher[0][0]][fresher[0][1]] = -1
        # room_tmp[fresher[1][0]][fresher[1][1]] = -1
        # print(dust)
        for r in range(R):
            for c in range(C):
                # r, c = dust[i][j]
                amount = room[r][c]
                spread_amount = amount // 5
                chk_move = 0 # 확산된 방향
                # 최대 네 방향으로 확산
                if spread_amount > 0:
                    for dt in range(4):
                        dr = r + delta[dt][0]
                        dc = c + delta[dt][1]
                        # 인접한 방향에 칸이 없거나 공기청정기가 있으면 확산이 일어나지 않음
                        if dr < 0 or dr >= R or dc < 0 or dc >= C: continue
                        if room[dr][dc] == -1: continue
                        room_tmp[dr][dc] += spread_amount
                        chk_move += 1
                # r, c에 남은 미세먼지 양
                room_tmp[r][c] += amount - spread_amount * chk_move

        return room_tmp
    room = spread(room)

    def clean(room, fresher):
        # 윗부분 반시계방향인데 시계방향으로 확인
        upper = fresher[0]
        # 좌측
        for i in range(upper[0] - 1, -1, -1): # 1, -1,-1 -> 1, 0
            if room[i + 1][0] != -1:
                room[i + 1][0] = room[i][0]
        # 상측
        for i in range(1, C):
            room[0][i - 1] = room[0][i]
        # 우측
        for i in range(1, upper[0] + 1): # 1, 0
            room[i - 1][C - 1] = room[i][C - 1]
        # 하측
        for i in range(C - 2, -1, -1):
            if i != 0:
                room[upper[0]][i + 1] = room[upper[0]][i]
            else:
                room[upper[0]][i + 1] = 0

        # 아래부분 시계방향인데 반시계방향으로 확인
        lower = fresher[1]
        # 좌측
        for i in range(lower[0] + 1, R): # 4,5,6
            if room[i - 1][0] != -1:
                room[i - 1][0] = room[i][0]
        # 하측
        for i in range(1, C):
            room[R - 1][i - 1] = room[R - 1][i]
        # 우측
        for i in range(R - 2, lower[0] - 1, -1):
            room[i + 1][C - 1] = room[i][C - 1]
        # 상측
        for i in range(C - 2, -1, -1):
            if i != 0:
                room[lower[0]][i + 1] = room[lower[0]][i]
            else:
                room[lower[0]][i + 1] = 0

    clean(room, fresher)
    
def arr_sum():
    ret = 2
    for i in range(R):
        for j in range(C):
            ret += room[i][j]
    return ret

print(arr_sum())

시뮬레이션 문제 참 못한다. 딱 일주일전에 풀어야할 문제를 지금까지 끌고왔다.

미세먼지가 확산하는것을 spread, 공기청정기가 돌아가는 것을 clean으로 만들어서 풀었는데 아무리봐도 틀린 알고리즘이 아닌데 계속 틀렸다. (맞는데 왜 틀리지....)

현재 코드에는 없는 부분이지만 오늘 새벽에 다시 디버깅하면서 dust_set으로 미세먼지가 어디있는지 확인 하는 부분이 잘못되었음을 찾게되었다.

spread 할때 까지는 미세먼지가 있는 부분이 같지만 clean을 하고 나면 한칸씩 이동하는 먼지가 있어서 이전에 받아놓았던 dust_set이 안맞았다.

그래서 반복문을 중첩 시켜서 모든 원소를 확인하는 방법을 사용하였고 통과하였다.