[BOJ][Python] 백준 17144번 : 미세먼지 안녕!

- 문제 링크

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

- 풀이

어제 올린 것과 같은 SW 역량 테스트 기출문제 중 하나이고, 구현 + 시뮬레이션 문제였다.

미세먼지를 확산시키는 함수, 위쪽 공기청정기 함수, 아래쪽 공기청정기 함수, 총 3개의 함수를 만들어서 사용했다.

 

1. 미세먼지를 확산시키는 함수

def chk():
    arr = [[0] * C for _ in range(R)]
    for i in range(R):
        for j in range(C):
            x, y = i, j
            count = 0
            if graph[i][j] == 0:
                continue
            if graph[i][j] == -1:
                arr[i][j] = -1
                continue         
            for k in range(4):
                nx = x + dx[k]
                ny = y + dy[k]
                if 0 <= nx < R and 0 <= ny < C and graph[nx][ny] != -1:
                    count += 1
                    arr[nx][ny] += graph[x][y] // 5
            arr[x][y] += (graph[x][y] - (graph[x][y] // 5) * count)

    for i in range(R):
        for j in range(C):
            graph[i][j] = arr[i][j]

미세먼지를 확산시키는 chk 함수다. 값을 임시로 저장해 놓을 arr 배열을 만들어준다. 그리고 미세먼지를 확산시키는 모든 과정을 arr 배열에 삼입 후, 확산시키는 과정이 끝난 후 원래 미세먼지 배열에 있는 값을 임시 배열에 있는 값으로 교체해 준다.

임시배열을 만들어서 처리하지 않으면 중간에 값이 변경되므로 임시배열을 만들어서 처리한다.

 

2. 위쪽 공기청정기 함수

def clean_top(x, y):
    for i in range(x-1, 0, -1):
        graph[i][0] = graph[i-1][0]
    
    for j in range(C-1):
        graph[0][j] = graph[0][j+1]
    
    for k in range(x):
        graph[k][C-1] = graph[k+1][C-1]

    for l in range(C-1, 1, -1):
        graph[x][l] = graph[x][l-1]

    graph[x][1] = 0

문제에서 공기청정기가 작동하는 방향은 아래 그림과 같다.

나는 문제에서 제시한 방향대로 하는 것보다, 그 방향의 반대로 하는 것이 더 구현이 쉬울 것 같아 반대방향으로 이동하면서 미세먼지를 한 칸씩 끌어오도록 구현했다. 미세먼지를 정화하는 것은 정화시키는 위치의 바로 위의 값을 대입해서 구현했다.

 

3. 아래쪽 공기청정기 함수

def clean_bottom(x, y):
    for i in range(x+1, R-1):
        graph[i][0] = graph[i+1][0]
    
    for j in range(C-1):
        graph[R-1][j] = graph[R-1][j+1]
    
    for k in range(R-1, x, -1):
        graph[k][C-1] = graph[k-1][C-1]

    for l in range(C-1, 1, -1):
        graph[x][l] = graph[x][l-1]

    graph[x][1] = 0

위에서 설명한 방법대로, 그림과 반대방향으로 이동하면서 미세먼지를 한칸씩 끌어오도록 구현했다. 

 

 

- 전체 코드

import sys
from collections import deque
input = sys.stdin.readline
dx = [0,0,-1,1]
dy = [-1,1,0,0]
R, C, T = map(int, input().split())

def clean_top(x, y):
    for i in range(x-1, 0, -1):
        graph[i][0] = graph[i-1][0]
    
    for j in range(C-1):
        graph[0][j] = graph[0][j+1]
    
    for k in range(x):
        graph[k][C-1] = graph[k+1][C-1]

    for l in range(C-1, 1, -1):
        graph[x][l] = graph[x][l-1]

    graph[x][1] = 0

def clean_bottom(x, y):
    for i in range(x+1, R-1):
        graph[i][0] = graph[i+1][0]
    
    for j in range(C-1):
        graph[R-1][j] = graph[R-1][j+1]
    
    for k in range(R-1, x, -1):
        graph[k][C-1] = graph[k-1][C-1]

    for l in range(C-1, 1, -1):
        graph[x][l] = graph[x][l-1]

    graph[x][1] = 0

def chk():
    arr = [[0] * C for _ in range(R)]
    for i in range(R):
        for j in range(C):
            x, y = i, j
            count = 0
            if graph[i][j] == 0:
                continue
            if graph[i][j] == -1:
                arr[i][j] = -1
                continue         
            for k in range(4):
                nx = x + dx[k]
                ny = y + dy[k]
                if 0 <= nx < R and 0 <= ny < C and graph[nx][ny] != -1:
                    count += 1
                    arr[nx][ny] += graph[x][y] // 5
            arr[x][y] += (graph[x][y] - (graph[x][y] // 5) * count)

    for i in range(R):
        for j in range(C):
            graph[i][j] = arr[i][j]

graph = []
clean = []
for i in range(R):
    graph.append(list(map(int, input().split())))

for i in range(R):
    for j in range(C):
        if graph[i][j] == -1:
            clean.append((i, j))


for i in range(T):
    chk()
    clean_top(clean[0][0], clean[0][1])
    clean_bottom(clean[1][0], clean[1][1])

res = 0
for i in range(R):
    for j in range(C):
        if graph[i][j] != -1:
            res += graph[i][j]

print(res)

 

공기청정기 기능 구현 부분에서 청소 범위 지정하는 것 때문에 애를 조금 먹었으나.. 그래도 맞추는 것은 성공하였다.

 

만약 값이 적은 범위 오차 내에서 이상하게 나온다면 공기청정기 기능에서 청소하는 범위가 잘못된 것은 아닌지 확인해 보면 좋을 듯하다.