[BOJ] 17144 미세먼지 안녕!

date

Jul 28, 2023

slug

boj-17144

author

status

Public

문제 링크

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

문제

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

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

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

미세먼지가 확산된다. 확산은 미세먼지가 있는 모든 칸에서 동시에 일어난다.

(r, c)에 있는 미세먼지는 인접한 네 방향으로 확산된다.

인접한 방향에 공기청정기가 있거나, 칸이 없으면 그 방향으로는 확산이 일어나지 않는다.

확산되는 양은 5이고 소수점은 버린다.

(r, c)에 남은 미세먼지의 양은 ×(확산된 방향의 개수) 이다.

공기청정기가 작동한다.

공기청정기에서는 바람이 나온다.

위쪽 공기청정기의 바람은 반시계방향으로 순환하고, 아래쪽 공기청정기의 바람은 시계방향으로 순환한다.

바람이 불면 미세먼지가 바람의 방향대로 모두 한 칸씩 이동한다.

공기청정기에서 부는 바람은 미세먼지가 없는 바람이고, 공기청정기로 들어간 미세먼지는 모두 정화된다.

다음은 확산의 예시이다.

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

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

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

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

방의 정보가 주어졌을 때, T초가 지난 후 구사과의 방에 남아있는 미세먼지의 양을 구해보자.

문제풀이

확산과 공기청정기 프로세스를 나누어 계산했다.

확산이 먼저 이루어지고 그 후 공기청정기가 순차적으로 동작하는 식

dx, dy 테크닉을 사용하여 구현을 좀 더 쉽게 하였고

확산과 공기청정기 바람이 이동 하는 방식에 있어서 pending_list를 사용하여

이해가 더 쉽게 하였다.

spreading_process()

모든 arr에 대하여

값이 5이상이면 spreading(y, x)
-1이면 공기청정기로 인식 (* 이건 함수밖에서 한번만 해도됨 *)

a가 끝나면 pending_list에 있는 것을 차례로 계산

spreading(y, x)

dx, dy 테크닉을 사용하여 상하좌우에 벽이거나 공기청정기가 아니면
문제에 주어진대로 확산, 단 확산된 값은 pending_list에 저장

air_cleaner_process()

공기청정기 바람 route에 대하여

1번에서 공기청정기로 인식한 값을 list에서 꺼내어 0이면 위쪽 공기청정기 1이면 아래쪽 공기청정기 위쪽 공기청정기는 반시계, 아래쪽은 시계방향 즉, dx, dy테크닉에서 (0,1,2,3 → 동북서남) 반시계방향은 (+1) 시계방향은 (-1)
벽일경우 방향을 공기청정기 바람 방향에 따라 바꾸어 pending list에 저장

공기청정기 바람이 공기청정기를 만나면 종료
이떄 공기청정기 바로 옆칸 부터 시작하므로, 옆칸에 대해서는 값이 그대로 있기때문에 0으로 초기화

air_cleaner()

pending_list에 있는 것들을 “역순”으로 꺼내어 계산한다.
역순으로 계산하지 않으면 값이 덮어 씌워지므로 마지막 값이 사라지게 된다.? 역순으로 안해도될듯? 안하니까 값이 달라집니다.. ㅇ뭐지..

파이썬 문제풀이 코드


import sys
input = sys.stdin.readline

dx = [1, 0, -1, 0] # 동북서남
dy = [0, -1, 0, 1] # 0123

arr = []

R, C, T = tuple(map(int, input().split()))

for _ in range(R):
    li = list(map(int, input().split()))
    arr.append(li)
    
# 확산 phase # 공기청정기 데이터도 같이 모음

def spreading_process():
    for i in range(R):
        for j in range(C):
            if arr[i][j] > 4: # 5보다 커야 확산이 일어남
                spreading(i, j)
            elif arr[i][j] == -1:
                air_cleaner_list.append((i, j))
                

    for spread in spreading_pending_list:
        y, x, value = spread  
        arr[y][x] += value
    

def spreading(y, x):
    count = 0
    for i in range(4):
        if x+dx[i] >= 0 and x+dx[i] < C and y+dy[i] >= 0 and y+dy[i] < R: # 벽을 안넘으면 확산
            if arr[y+dy[i]][x+dx[i]] == -1: # 공기청정기로는 확산이 안됨
                continue 
            spreading_pending_list.append((y+dy[i], x+dx[i], arr[y][x]//5))
            count += 1
    arr[y][x] = arr[y][x] - (arr[y][x]//5)*count 
    
    
    
    
# 공기 청정기 phase
def air_cleaner():
    # print(pending_air_cleaner_list[::-1])
    # print(arr)
    for air_clean in pending_air_cleaner_list[::-1]: # 역으로 해야 순서가 안꼬임
        y, x, value, d = air_clean
        if arr[y+dy[d]][x+dx[d]] == -1:
            arr[y][x] = 0
        else:
            arr[y+dy[d]][x+dx[d]] = value
        # print(arr[0])
            
def air_cleaner_process():
    global pending_air_cleaner_list
    for idx in range(2):
        if idx == 0: # 위쪽 공기 청정기
            y, x = air_cleaner_list[idx]
            cur_y, cur_x = y, x+1 # 처음은 동쪽
            d = 0
            # arr[cur_y][cur_x] = d
            while arr[cur_y][cur_x] != -1:
                if cur_x+dx[d] >= 0 and cur_x+dx[d] < C and cur_y+dy[d] >= 0 and cur_y+dy[d] < R: # 벽아니면 방향 그대로
                    pending_air_cleaner_list.append((cur_y, cur_x, arr[cur_y][cur_x], d))
                    cur_y, cur_x = cur_y+dy[d], cur_x+dx[d]
                    # print(cur_y, cur_x)
                    #air_cleaner_matrix[cur_y+dy[d]][cur_x+dx[d]] = d # 방향만 가지고 있음
                else: # 벽이면 회전
                    d = (d+1)%4
            y, x = air_cleaner_list[idx]
            arr[y][x+1] = 0
        elif idx == 1: # 아래쪽 공기 청정기
            y, x = air_cleaner_list[idx]
            cur_y, cur_x = y, x+1 # 처음은 동쪽
            d = 0
            # arr[cur_y][cur_x] = d
            while arr[cur_y][cur_x] != -1:
                if cur_x+dx[d] >= 0 and cur_x+dx[d] < C and cur_y+dy[d] >= 0 and cur_y+dy[d] < R: # 벽아니면 방향 그대로
                    pending_air_cleaner_list.append((cur_y, cur_x, arr[cur_y][cur_x], d))
                    cur_y, cur_x = cur_y+dy[d], cur_x+dx[d]
                    #air_cleaner_matrix[cur_y+dy[d]][cur_x+dx[d]] = d # 방향만 가지고 있음
                else: # 벽이면 회전 -90도
                    d = (d-1)
                    if d < 0:
                        d = 3
            y, x = air_cleaner_list[idx]
            arr[y][x+1] = 0
                        
        air_cleaner()
        pending_air_cleaner_list = []
    

for _ in range(T):
    # reset
    spreading_pending_list = []
    air_cleaner_list = []
    pending_air_cleaner_list = []
    spreading_process()
    # print(air_cleaner_list)
    air_cleaner_process()
    
# print(arr)
print(sum([sum(i) for i in arr]) + 2)

시간복잡도

O(n^2)

Brute-Force

입력

첫째 줄에 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초가 지난 후 구사과 방에 남아있는 미세먼지의 양을 출력한다.

예제 입력


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

예제 출력


7 8 2
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


7 8 50
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

알고리즘 분류

구현

시뮬레이션