백준 미세먼지 안녕! [17144] 파이썬(Python) 코드 + 해설

백준 17144 미세먼지 안녕! 문제

 

문제 분석

구사과는 방에 있는 미세먼지를 제거하기 위해 공기청정기를 설치하려고 한다. 방은 R×C 크기의 격자판으로 이루어져 있고, 각 칸에는 미세먼지가 있을 수 있다. 공기청정기는 항상 첫 번째 열에 설치되어 있으며, 두 개의 연속된 행을 차지한다.

1초 동안 다음과 같은 일이 순서대로 일어난다:

1. 미세먼지 확산:
   • 미세먼지는 인접한 네 방향으로 확산된다.
   • 확산되는 양은 현재 칸의 미세먼지 양을 5로 나눈 값의 몫이다 (즉, ⌊Ar,c/5⌋).
   • 공기청정기가 있거나 칸이 없으면 그 방향으로 확산되지 않는다.
   • 확산된 후 남은 미세먼지의 양은 Ar,c−(확산된 양×확산된 방향의 개수)이다.
2. 공기청정기 작동:
   • 위쪽 공기청정기는 반시계 방향으로 순환한다.
   • 아래쪽 공기청정기는 시계 방향으로 순환한다.
   • 바람이 불면서 미세먼지가 한 칸씩 이동한다.
   • 공기청정기로 들어간 미세먼지는 모두 정화된다.

T초 후에 방에 남아있는 미세먼지의 총량을 구하는 것이 목표다.

문제 접근

이 문제는 시뮬레이션 문제이다. 각 시간마다 미세먼지의 확산과 공기청정기의 작동을 구현해야 한다.

주요 단계는 다음과 같다:

1. 입력 처리 및 초기화:
   • 방의 상태를 저장하고, 공기청정기의 위치를 파악한다.
2. 시간 순환:
   • T초 동안 아래의 과정을 반복한다:
     • 미세먼지 확산을 구현한다.
     • 공기청정기의 작동을 구현한다.
3. 결과 출력:
   • 모든 시간이 지난 후 방에 남아있는 미세먼지의 총량을 계산한다.

알고리즘 구현

1. 입력 처리 및 초기화

• 방의 상태를 2차원 배열로 저장한다.
• 공기청정기의 위치(두 행)를 찾는다.

import sys
input = sys.stdin.readline

R, C, T = map(int, input().split())
room = []
air_cleaner = []

for i in range(R):
    row = list(map(int, input().split()))
    room.append(row)
    if row[0] == -1:
        air_cleaner.append(i)

 

2. 미세먼지 확산 구현

• 각 칸의 미세먼지 확산을 계산하기 위해 확산 결과를 저장할 임시 배열을 사용한다.
• 모든 칸을 순회하며 미세먼지가 있는 경우 확산을 계산한다.

def spread_dust():
    dx = [-1, 1, 0, 0]  # 상하좌우
    dy = [0, 0, -1, 1]
    temp = [[0]*C for _ in range(R)]
    for x in range(R):
        for y in range(C):
            if room[x][y] >= 5:
                amount = room[x][y] // 5
                for i in range(4):
                    nx = x + dx[i]
                    ny = y + dy[i]
                    if 0 <= nx < R and 0 <= ny < C and room[nx][ny] != -1:
                        temp[nx][ny] += amount
                        room[x][y] -= amount
    for x in range(R):
        for y in range(C):
            room[x][y] += temp[x][y]

3. 공기청정기 작동 구현

• 위쪽 공기청정기는 반시계 방향으로 순환한다.
• 아래쪽 공기청정기는 시계 방향으로 순환한다.
• 각 방향에 따라 미세먼지를 이동시킨다.

def operate_air_cleaner():
    upper = air_cleaner[0]
    lower = air_cleaner[1]
    
    # 위쪽 공기청정기 (반시계 방향)
    # 아래로 당기기
    for i in range(upper-1, 0, -1):
        room[i][0] = room[i-1][0]
    # 왼쪽으로 당기기
    for i in range(C-1):
        room[0][i] = room[0][i+1]
    # 위로 당기기
    for i in range(upper):
        room[i][C-1] = room[i+1][C-1]
    # 오른쪽으로 당기기
    for i in range(C-1, 1, -1):
        room[upper][i] = room[upper][i-1]
    room[upper][1] = 0  # 공기청정기에서 정화된 공기
    
    # 아래쪽 공기청정기 (시계 방향)
    # 위로 당기기
    for i in range(lower+1, R-1):
        room[i][0] = room[i+1][0]
    # 왼쪽으로 당기기
    for i in range(C-1):
        room[R-1][i] = room[R-1][i+1]
    # 아래로 당기기
    for i in range(R-1, lower, -1):
        room[i][C-1] = room[i-1][C-1]
    # 오른쪽으로 당기기
    for i in range(C-1, 1, -1):
        room[lower][i] = room[lower][i-1]
    room[lower][1] = 0  # 공기청정기에서 정화된 공기

4. 전체 시뮬레이션

for _ in range(T):
    spread_dust()
    operate_air_cleaner()

5. 결과 계산 및 출력

• 방에 남아있는 미세먼지의 총량을 계산한다.

total_dust = 0
for i in range(R):
    for j in range(C):
        if room[i][j] > 0:
            total_dust += room[i][j]
print(total_dust)

백준 17144 미세먼지 안녕! 문제 정답 파이썬(Python) 코드

import sys
input = sys.stdin.readline

R, C, T = map(int, input().split())
room = []
air_cleaner = []

for i in range(R):
    row = list(map(int, input().split()))
    room.append(row)
    if row[0] == -1:
        air_cleaner.append(i)

def spread_dust():
    dx = [-1, 1, 0, 0]  # 상하좌우
    dy = [0, 0, -1, 1]
    temp = [[0]*C for _ in range(R)]
    for x in range(R):
        for y in range(C):
            if room[x][y] >= 5:
                amount = room[x][y] // 5
                for i in range(4):
                    nx = x + dx[i]
                    ny = y + dy[i]
                    if 0 <= nx < R and 0 <= ny < C and room[nx][ny] != -1:
                        temp[nx][ny] += amount
                        room[x][y] -= amount
    for x in range(R):
        for y in range(C):
            room[x][y] += temp[x][y]

def operate_air_cleaner():
    upper = air_cleaner[0]
    lower = air_cleaner[1]
    
    # 위쪽 공기청정기 (반시계 방향)
    # 아래로 당기기
    for i in range(upper-1, 0, -1):
        room[i][0] = room[i-1][0]
    # 왼쪽으로 당기기
    for i in range(C-1):
        room[0][i] = room[0][i+1]
    # 위로 당기기
    for i in range(upper):
        room[i][C-1] = room[i+1][C-1]
    # 오른쪽으로 당기기
    for i in range(C-1, 1, -1):
        room[upper][i] = room[upper][i-1]
    room[upper][1] = 0  # 공기청정기에서 정화된 공기
    
    # 아래쪽 공기청정기 (시계 방향)
    # 위로 당기기
    for i in range(lower+1, R-1):
        room[i][0] = room[i+1][0]
    # 왼쪽으로 당기기
    for i in range(C-1):
        room[R-1][i] = room[R-1][i+1]
    # 아래로 당기기
    for i in range(R-1, lower, -1):
        room[i][C-1] = room[i-1][C-1]
    # 오른쪽으로 당기기
    for i in range(C-1, 1, -1):
        room[lower][i] = room[lower][i-1]
    room[lower][1] = 0  # 공기청정기에서 정화된 공기

for _ in range(T):
    spread_dust()
    operate_air_cleaner()

total_dust = 0
for i in range(R):
    for j in range(C):
        if room[i][j] > 0:
            total_dust += room[i][j]
print(total_dust)

 

백준 17144 미세먼지 안녕! 문제 제출 결과

 

 

백준 17144 안녕 미세먼지! 제출 결과

 

도움이 되셨다면 공감과 댓글 부탁드립니다.