[백준] 17144 미세먼지 안녕!

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 이해 및 접근

크게 미세먼지가 확산되는 이동과 공기청정기가 가동되어 미세먼지가 이동하는 두개의 함수로 나누어서 작성하였습니다.

Python 으로 제출하였을 경우 시간초과 문제가 발생하였습니다. PyPy 로 제출하여 통과하였습니다.

 

추후에 단순 2중 반복문이 아닌 미세먼지가 현재 있는 위치만 기록하여 반복시키는 방법을 이용하여 다시 풀이할 예정입니다.

2) 알고리즘

• 구현

3) 풀이 코드

사용 언어 - Python

import sys
sys.stdin = open('input.txt')

R, C, T = map(int, sys.stdin.readline().split())                                # 행, 열, 시간
board = [list(map(int, sys.stdin.readline().split())) for _ in range(R)]        # 초기 입력값
cleaner = []                                                                    # 공기청정기 위치

dr = [-1, 0, 1, 0]                              # 위 오른쪽 아래 왼쪽
dc = [0, 1, 0, -1]

for i in range(R):                              # 공기청정기 위치 찾기
    if board[i][0] == -1:
        cleaner.append((i, 0))

def dust_move(board):                           # 미세먼지 이동 함수
    new_board = [[0] * C for _ in range(R)]     # 미세먼지가 이동한 결과를 담을 새로운 2차원 배열
    
    for i in range(R):
        for j in range(C):
            if (i, j) in cleaner:               # 공기청정기 좌표라면, -1 로 지정
                new_board[i][j] = -1
            elif board[i][j] > 0:               # 미세먼지가 있으면
                amount = board[i][j] // 5       # 이동될 먼지 양
                remain = board[i][j]            # 현재 위치에 남은 먼지 양
                for k in range(4):
                    r = i + dr[k]
                    c = j + dc[k]

                    if 0 <= r < R and 0 <= c < C and board[r][c] != -1:     # 주변 좌표가 정상적이고 공기청정기가 아닐때
                        remain -= amount                                    # 현재 위치 남은 먼지양 줄이기
                        new_board[r][c] += amount                           # 이동한 결과를 담을 배열에 이동된 먼지양 추가
                new_board[i][j] += remain                                   # 현재 좌표의 남은 먼지양 추가

    return new_board

def air_cleaner(y, x, k, direction, dust):                                  # 공기청정기 가동 (현재 좌표, 위쪽 공기청정기 or 아래쪽 공기청정기
                                                                            # 진행방향, 먼지양)
    if y == cleaner[k][0] and x == cleaner[k][1]:                           # 공기청정기로 들어왔으면 종료
        return
    elif not (0 <= y < R and 0 <= x < C):                                   # 범위를 벗어나는 좌표라면 진행 방향 회전
        y -= dr[direction]
        x -= dc[direction]
        direction = (direction - 1) % 4 if not k else (direction + 1) % 4
        y += dr[direction]
        x += dc[direction]
        air_cleaner(y, x, k, direction, dust)
    else:                                                                   # 먼지 한칸씩 이동
        move_dust = board[y][x]
        board[y][x] = dust
        y += dr[direction]
        x += dc[direction]
        air_cleaner(y, x, k, direction, move_dust)

while T > 0:                                                            # 시간이 남았다면 반복
    T -= 1

    board = dust_move(board)                                            # 먼지 이동
    air_cleaner(cleaner[0][0], cleaner[0][1]+1, 0, 1, 0)                # 위쪽 공기청정기 가동
    air_cleaner(cleaner[1][0], cleaner[1][1]+1, 1, 1, 0)                # 아래쪽 공기청정기 가동

answer = 2                      # 공기청정기의 좌표값이 -1 이므로 초기값은 2로 설정
for i in range(R):
    answer += sum(board[i])

print(answer)

---

📝 결과 및 학습한 내용

1) 어려웠던 내용

Python 으로 제출 시 시간초과 문제가 발생하였습니다.

시간 초과 문제를 해결하기 위하여 미세먼지 확산을 계산하는 반복문을 줄이고 싶었으나 접근이 어려웠습니다.

2) 새롭게 학습한 내용

특별히 없습니다.

---

🔗 문제 링크

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

17144번: 미세먼지 안녕!

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다