[Python] 백준 17144번 문제 풀이 - 미세먼지 안녕!

문제 링크

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

 

문제 이해

이 문제는 특정 시간이 지난후에 남아있는 미세먼지 양이 얼마나 되는지 출력하면 되는 문제입니다.

미세먼지는 주변 상하좌우 칸으로 //5 만큼 해서 이동합니다.

상하좌우로 갈 때 맵을 벗어나거나 공기청정기가 있다면 확산하지 않습니다.

(1,1)에 있는 미세먼지는 (0,1), (1,0), (2,1), (1,2)가 가능하여 4방향으로 확산하고

(0,0)에 있는 미세먼지는 (1,0)과 (0,1)로 확산합니다.

 

그리고 또 중요한것은 미세먼지는 누적되서 확산하는 것이 아닌 동시에 확산되는 점입니다.

이게 무슨 말이냐 하면

다음 그림을 보면서 설명하겠습니다.

 

(0,1) 에는 30이 있습니다. 30이 확산될 칸은 (0,0), (0,2), (1,1)이 있는데요 //5 하면 각 칸마다 미세먼지가 6씩 확산됩니다.

기존 칸에는 확산된만큼 빼줍니다.

그러면 (0,0)에 6, (0,1)에 12, (0,2)에 13, (1,1)에 16이 됩니다.

6 12 13
-1 16 0
-1 0 20

그래서 다음 미세먼지가 있던 (0,2)로 이동하면 7에 6이 누적되어 13이 되었다고 //5 해서 2가 이동하는 것이 아닙니다.

한꺼번에 퍼지기 때문에 (0,1)과 (1,2)에 1씩 확산되고 (0,2)에는 2가 빠지는 것입니다.

 

정리하면 30은 주변 세 칸에 6씩 확산시키고 원래 자신은 18이 빠지는거고

7은 주변 두 칸에 1씩 확산시키고 자신은 2가 빠지는 거고

10은 공기청정기를 제외한 주변 세 칸에 2씩 확산시키고 자신은 6이 빠지는 것입니다.

 

그리고 공기청정기는 높이가 2인데 위쪽 청정기는 반시계 방향으로 순환하고 아래청정기는 시계방향으로 순환합니다.

공기청정기는 1초에 한칸씩 이동합니다.

그래서 1초가 지날때마다 위쪽 청정기의 위칸(2,1)에 있는 먼지가 사라지고, 아래쪽 청정기의 아래칸(5,1)에 있는 먼지가 사라집니다.

아이디어

이것을 구현하기 위한 아이디어는 다음과 같습니다.

1. T초간 반복문을 돌린다.
2. 먼지확산 함수를 돌린다.
   1. 주변에 //5만큼 확산시키고
   2. 확산시킨만큼 미세먼지를 빼서 새로운 배열에 더해준다.
3. 위쪽 공기청정기를 작동시킨다.
   1. 반시계 방향으로 미세먼지를 한칸씩 이동시킨다.
4. 아래쪽 공기청정기를 작동시킨다.
   1. 시계 방향으로 미세먼지를 한칸씩 이동시킨다.

시간복잡도

우선 T만큼 반복문을 돌고 그 내부에서 3개의 함수가 돌아가기 때문에 시간복잡도는 다음과 같습니다.

T는 1000이고 바이러스 확산되는 횟수는 O(n^2) 50X50X4 하니 10000

위쪽, 아래쪽 공기청정기 도는 횟수는 49 + 25 + 50 + 24 대략 300

10300 X 1000하면 10,300,000

1000만회 돌기 때문에 1초의 2000만번 이하이기 때문에 가능합니다.

코드 구현

import sys
input = sys.stdin.readline

r, c, t = map(int, input().split())

rooms = []
air_conditioner = []
for i in range(r):
    data = list(map(int, input().split()))
    rooms.append(data)

    for j in range(c):
        if data[j] == -1:
            air_conditioner.append((i,j))
# 시계방향
dy = [0, 1, 0, -1]
dx = [1, 0, -1, 0]

# 반시계방향
top_dy = [0, -1, 0, 1]
top_dx = [1, 0, -1, 0]

# 먼지 확산 함수
def dust_spread(rooms):
    # 새로운 배열 준비
    new_rooms = [[0] * c for _ in range(r)]

    for y in range(r):
        for x in range(c):
            if rooms[y][x] > 0:
                spreaded_dust = 0
                for k in range(4):
                    ny = y + dy[k]
                    nx = x + dx[k]
                    
                    # 범위 내에 있거나 공기청정기가 아닐 때
                    if (0<=ny<r) and (0<=nx<c) and rooms[ny][nx] != -1:
                        spreaded_dust += (rooms[y][x] // 5) # 확산한 먼지 저장
                        new_rooms[ny][nx] += (rooms[y][x] // 5) # 주변 칸으로 확산
                
                # 원래 먼지 - 확산한 먼지로 업데이트
                new_rooms[y][x] += (rooms[y][x] - spreaded_dust)
    
    # 원래 공기청정기가 있었던 위치는 -1로 만들고
    for element in air_conditioner:
        ay, ax = element
        new_rooms[ay][ax] = -1
    
    # 확산한 방정보 리턴
    return new_rooms

# 위쪽 공기청정기 함수
def top_air_conditioner(depth, y, x, prev):
    # print(f"현재 depth : {depth}, y : {y}, x : {x}, prev : {prev} 현재 값 : {rooms[y][x]}")
    ny = y + top_dy[depth]
    nx = x + top_dx[depth]
    
    # 범위 내에 있을 때
    if (0 <= ny < r) and (0 <= nx < c):
        # 공기청정기로 들어가면 함수 끝
        if rooms[ny][nx] == -1:
            rooms[y][x] = prev
            return
        
        # 먼지 다음칸으로 이동시키기
        next = rooms[y][x]
        rooms[y][x] = prev
        top_air_conditioner(depth, ny, nx, next)
    else: # 범위 밖으로 나갈 때
        # 반시계로 방향을 바꿔서 진행
        top_air_conditioner(depth + 1, y, x, prev)
        return  # 이 depth는 종료

# 아래쪽 공기청정기 함수(위쪽 공기청정기 함수에서 방향만 시계방향으로)
def bottom_air_conditioner(depth, y, x, prev):
    # print(f"현재 depth : {depth}, y : {y}, x : {x}, prev : {prev} 현재 값 : {rooms[y][x]}")
    ny = y + dy[depth]
    nx = x + dx[depth]

    if (0 <= ny < r) and (0 <= nx < c):
        # 공기청정기로 들어가면 함수 끝
        if rooms[ny][nx] == -1:
            rooms[y][x] = prev
            return

        next = rooms[y][x]
        rooms[y][x] = prev

        bottom_air_conditioner(depth, ny, nx, next)
    else:
        bottom_air_conditioner(depth + 1, y, x, prev)
        return  # 이 depth는 종료

# 위 아래 공기 청정기 좌표 가져오기
top_y, top_x = air_conditioner[0]
bottom_y, bottom_x = air_conditioner[1]

# t만큼 반복문
for _ in range(t):
    rooms = dust_spread(rooms) # 먼지 확산
    top_air_conditioner(0, top_y, top_x+1, 0) # 위쪽 공기청정기 작동
    bottom_air_conditioner(0, bottom_y, bottom_x+1, 0) # 아래쪽 공기청정기 작동

# 배열의 모든 요소 더하기
answer = 0
for x in rooms:
    answer += sum(x)

# 모든 요소 더한것에서 공기청정기로 -2되어 결과 나온거 +2해서 출력
print(answer+2)

느낀 점

이 문제는 그래도 다른 블로그 참고하지 않고 스스로 풀어낸 문제라 뿌듯합니다.

하지만 공기청정기로 시계방향, 반시계방향으로 먼지를 이동시키는 것을 구현하는 것이 꽤 힘들었습니다.

다음 값을 저장하고 넘기는 것이 아직은 머리속으로 쉽게 그려지지 않아서 구현 문제를 더 많이 풀어보면서 재귀함수를 호출하는 것에 대해 익숙해져야겠다고 느꼈습니다.