백준 17144) 미세먼지 안녕!_Python

문제 분석

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

17144번: 미세먼지 안녕!

• 모든 조건을 다 확인하면서 구현해내는게 중요한 Simulation 문제!

코드

# 삼성기출
import sys

input = sys.stdin.readline

R, C, T = map(int, input().split())  # R행 C열
board = [list(map(int, input().split())) for _ in range(R)]

cleaner = []
for i in range(R):
    if board[i][0] == -1:
        cleaner.append((i, 0))

def dust_diffusion():
    diffusion = [[0]*C for _ in range(R)]
    dx = [-1, 0, 0, 1]  # 미세먼지 상하좌우
    dy = [0, -1, 1, 0]

    for i in range(R):
        for j in range(C):
            if(board[i][j] != 0 and board[i][j] != -1):
                tmp = 0
                for k in range(4):
                    nx, ny = i+dx[k], j+dy[k]
                    if 0 <= nx < R and 0 <= ny < C and board[nx][ny] != -1:
                        tmp += board[i][j]//5
                        diffusion[nx][ny] += board[i][j]//5
                        # 상하좌우로 확산되는 경우 , 동시에 일어나고 근원지에서만 확산되므로 겹치지 않게 따로 계산

                board[i][j] -= tmp

    for i in range(R):
        for j in range(C):
            board[i][j] += diffusion[i][j]

def dust_clean_up():  # 위쪽 공기청정기, 반시계 방향
    dx = [0, -1, 0, 1]
    dy = [1, 0, -1, 0]
    curX, curY = cleaner[0][0], 1
    direction = 0
    prev = 0  # 처음 시작은 공기청정기이므로 미세먼지가 없다
    while True:
        nextX, nextY = curX+dx[direction], curY+dy[direction]
        if curX == cleaner[0][0] and curY == 0:
            break
        if nextX < 0 or nextY >= C or nextY < 0 or nextX >= R:
            direction += 1
            continue

        # 이전 칸의 먼지가 현재 칸으로 이동한다 swap, prev에는 현재 값이 저장된다.
        board[curX][curY], prev = prev, board[curX][curY]
        curX, curY = nextX, nextY

    return

def dust_clean_down():  # 아래쪽 공기청정기, 시계 방향
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]
    curX, curY = cleaner[1][0], 1
    direction = 0
    prev = 0  # 처음 시작은 공기청정기이므로 미세먼지가 없다
    while True:

        nextX, nextY = curX+dx[direction], curY+dy[direction]
        if curX == cleaner[1][0] and curY == 0:
            break  # X는 8이상 Y는 7이상
        if nextX < 0 or nextY >= C or nextY < 0 or nextX >= R:  # R가 7 C가 8이상이면
            direction += 1  # 다음 위치가 보드를 벗어나면 방향 전환
            continue

        # 이전 칸의 먼지가 다음칸으로 이동한다 swap
        board[curX][curY], prev = prev, board[curX][curY]
        curX, curY = nextX, nextY

    return

for _ in range(T):
    dust_diffusion()
    dust_clean_up()
    dust_clean_down()

ans = 0
for i in range(R):
    for j in range(C):
        if board[i][j] > 0:
            ans += board[i][j]

print(ans)

 

 

문제 풀이 과정

• T초 동안 미세먼지 제거를 위해 일련의 과정을 수행한다.
  • 미세먼지 확산
    • 중요한 것은 확산이 동시에 한번에 일어난다는 것이다. 따라서 초기 근원지(기존 배열)에서만 발생하고, 이후에 확산된 것은 따로 퍼지거나 영향을 끼치지 않는다. 배열을 순회를 돌더라도, 기존 근원지와 확산된 부분은 따로 관리해주자.
    • 따라서 근원지에서 확산된 양을 저장하는 diffusion 배열과 기존의 미세먼지에서 확산된 양을 뺀 기존 배열을 더해주어야 한다.
  • 위쪽 공기청정기 반시계 방향으로 순환
    • 바람이 반시계 방향으로 순환하며, 먼지가 바람 방향으로 한칸씩 이동하게 된다. 마지막 먼지는 공기청정기로 들어간다.
    • 여기서 방향을 바꿔주는 순간이 중요한데, 만약 현재 위치가 배열을 벗어나게 되면 그때마다 방향을 바꾸게 된다.
    • 공기 이동은 prev,cur=cur,prev 식으로 swap을 통해 이전 값을 현재 칸으로 옮기고, 현재 값은 저장해둔다.
  • 아래쪽 공기청정기 시계 방향으로 순환
    • 방향만 반대고, 로직은 똑같음.

 

PyPy3로 제출하였으며, Python3로는 통과하지 못하는 것 같다. 상당히 노가다성인 문제