[백준 17144번] 미세먼지 안녕! - 파이썬

 

① 문제 링크

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

17144번: 미세먼지 안녕!

---

② 알고리즘 분류

구현, 시물레이션

---

③ ★문제풀이 Point★

1. 문제에서 요구하는 내용 그대로 충실히 코드 구현하기

2. 공기청정기 바람 이동은 파이썬의 swap(변수 바꾸기) 이용하기

---

④ 풀이

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

문제에서 요구하는 대로 먼저 미세먼지의 확산 함수(dust_diffusion)를 만들어보자.

미세먼지의 확산은 확산이 이루어진 새로운 배열(diffusion)에 남아 있는 미세먼지의 배열(board)을 합쳐주면 된다.

그다음으로 공기청정기가 작동하는 방법에 대해 생각해보자.

공기청정기 바람이동

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

=> 처음 바꿔주는 변수(previous)를 0으로 놓는다.

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

=> 파이썬의 swap방식을 이용해 두 변수(board[x][y], previous)를 바꾼다.

바람이 두 가지 방향으로 순환하므로, 시계 방향(dust_clean_up)과 반시계 방향(dust_clean_down) 2개 함수를 만든다.

이제 코드를 작성해보자.

---

⑤ 코드

다음 코드는 PyPy3로 작성하였습니다.

# 17144번 미세먼지 안녕!

import sys
input = sys.stdin.readline

r, c, t = map(int, input().split())
board, cleaner = [], []

for i in range(r):
    board.append(list(map(int, input().split())))
    for j in range(len(board[i])):
        # 공기청정기 위치 받기
        if board[i][j] == -1:
            cleaner.append((i, j))


# 미세먼지 확산 함수 생성
def dust_diffusion():
    # 상, 하, 좌, 우 방향 표시
    steps = [[-1, 0], [1, 0], [0, -1], [0, 1]]
    # 각 위치마다 확산되는 미세먼지 양 표시
    diffusion = [[0] * c for _ in range(r)]
    # 확산
    for i in range(r):
        for j in range(c):
            if not (board[i][j] == 0 or board[i][j] == -1):
                turn = 0
                for dx, dy in steps:
                    nx, ny = i + dx, j + dy
                    if 0 <= nx < r and 0 <= ny < c and (nx, ny) not in cleaner:
                        turn += 1
                        diffusion[nx][ny] += board[i][j] // 5
                board[i][j] = board[i][j] - (board[i][j] // 5 * turn)
    # 남은 미세먼지 양 계산
    for i in range(r):
        for j in range(c):
            board[i][j] += diffusion[i][j]
    return

# 공기청정기 바람 방향이 반시계 방향으로 이동
def dust_clean_up():
    # 동, 북, 서, 남 방향
    up_step = [[0, 1], [-1, -0], [0, -1], [1, 0]]
    # 방향 바꾸기
    direct = 0
    # 공기청정기 위쪽 위치
    x, y = cleaner[0]
    # 시작 위치 행 좌표
    up, y = x, 1
    # 이전 값
    previous = 0
    while True:
        # 이동 위치 확인
        nx, ny = x + up_step[direct][0], y + up_step[direct][1]
        # 처음 위치로 되돌아오면 종료
        if x == up and y == 0:
            break
        # 맵을 벗어나는 곳이라면
        if nx < 0 or nx >= r or ny < 0 or ny >= c:
            # 방향 바꾸고 건너뛰기
            direct += 1
            continue
        # 두 변수 값 바꾸기(swap)
        board[x][y], previous = previous, board[x][y]
        # 다음 위치로 이동
        x, y = nx, ny
    return

# 공기청정기 바람 방향이 시계 방향으로 이동
def dust_clean_down():
    # 동, 남, 서, 북 방향
    down_step = [[0, 1], [1, 0], [0, -1], [-1, 0]]
    # 방향 바꾸기
    direct = 0
    # 공기청정기 아래쪽 위치
    x, y = cleaner[1]
    # 시작 위치 행 좌표
    down, y = x, 1
    # 이전 값
    previous = 0
    while True:
        # 이동 위치 확인
        nx, ny = x + down_step[direct][0], y + down_step[direct][1]
        # 처음 위치로 되돌아오면 종료
        if x == down and y == 0:
            break
        # 맵을 벗어나는 곳이라면
        if nx < 0 or nx >= r or ny < 0 or ny >= c:
            # 방향 바꾸고 다음 코드부터 건너뛰기
            direct += 1
            continue
        # 두 변수 값 바꾸기(swap)
        board[x][y], previous = previous, board[x][y]
        # 다음 위치로 이동
        x, y = nx, ny
    return

# T초 후까지 반복
for _ in range(t):
    dust_diffusion()
    dust_clean_up()
    dust_clean_down()

# T초 후에 남아있는 미세먼지의 양 총합 계산
ans = 0
for i in range(r):
    for j in range(c):
        if board[i][j] > 0:
            ans += board[i][j]

# 답 출력
print(ans)

 

17144 파이썬 미세먼지 안녕! 채점결과

 

---

⑥ 마치며

시물레이션, 구현 알고리즘 문제들은 문제이해가 우선임을 느꼈다. 이 문제를 풀면서 시간이 많이 걸렸다.

구현은 정말 뇌로는 이해가 되고 코드를 짤 수 있을 거 같은데, 막상 손으로 코드를 짜면 잘 안 되는 점이 많다.

이러한 구현 문제들을 많이 풀어보면서 좀 더 성장해 나가야겠다.

 

 

17144 미세먼지 안녕!