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

🔔 문제

백준 17144번 미세먼지 안녕!

🎯 풀이방법

⭐ 주의할 점은 미세먼지를 확장할 때, 현재 초에서 미세먼지가 있는 칸에서만 확산된다! 구체적으로는 확산될 값과 현재 미세먼지 값을 혼용하면 안된다!

예를들어, 위의 예시를 (0,0) ~ (R-1,C-1)까지 순차적으로 계산하면 다음과 같다.

현재 미세먼지양과 확산될 미세먼지양을 구분해서 생각해야 한다! 처음에 이걸 예상못해서 틀렸었다.

📌 pseudo code

1. 미세먼지가 있는 모든 칸에서의 확산
   1-1. 현재 미세먼지가 없거나 공기청정기면 pass
   1-2. 상,하,좌,우로 완전탐색
   1-3. 만약 공기청정기가 있고 범위 밖이면 확산 X 아니면 확산 O
   1-4. 현재 남아있는 미세먼지양 update

2. 위쪽을 반시계 방향으로 공기청정기 작동
   2-1. 다음 방문할 위치가 범위 내이면 방문. (위치 update)
   2-2. 현재 위치에 이전값을 넣는다
   2-3. 이전값 update
   2-4. 2-2~2-4 과정을 모든 사방면을 탐색할 때까지 반복

3. 아래쪽을 시계방향으로 작동
   (방향만 다르고 작동 과정은 2번과 동일함)

4. 1~3 과정을 1초 ~ T초 동안 반복

5. 총 미세먼지 양 계산
   
   

💡 이 문제를 통해 얻어갈 것

기본적인 시뮬레이션 문제

💻 Python code

메모리 128676 KB, 시간 432 ms, 코드길이 2726 B

import math

# 상, 하, 좌, 우
dr = [-1,1,0,0]
dc = [0,0,-1,1]

R, C, T = map(int, input().split())

board = []
for r in range(R):
    board.append(list(map(int, input().split())))

def printBoard():
    for b in board:
        for c in b:
            print(c, end=' ')
        print()

def spreadDust(airTop, airDown, origin):
    results = [[0]*C for _ in range(R)]
    for r in range(R):
        for c in range(C):
            if origin[r][c] <= 0:  # 없거나 공기청정기
                continue

            # 미세먼지 확산!
            curDust = origin[r][c]
            totalDir = 0
            for d in range(4):  # 상하좌우 탐색
                nr = r + dr[d]
                nc = c + dc[d]

                if nr<0 or nr>=R or nc<0 or nc>=C:  # 범위 밖인가?
                    continue
                if (nr, nc) == airTop or (nr, nc) == airDown:  # 공기청정기인가?
                    continue

                results[nr][nc] += math.trunc(curDust/5)
                totalDir += 1

            if totalDir > 0: # 현재 미세먼지 양 update
                results[r][c] += curDust-math.trunc(curDust/5)*totalDir
    return results


def check(r, c, origin):
    # 범위 밖인가?
    if r<0 or r>=R or c<0 or c>=C:
        return False

    # 공기청정기 원래 위치인가?
    if r == origin[0] and c == origin[1]:
        return False
    return True


def workAirPurifier(airLoc, dir):
    r, c = airLoc[0], airLoc[1]
    before, curDir = 0, 0

    while curDir < 4:
        # 범위 내일 때까지 현재 방향대로 증가
        while check(r+dir[curDir][0], c+dir[curDir][1], airLoc):
            # 위치 update
            r += dir[curDir][0]
            c += dir[curDir][1]

            # 현재 위치에 이전값 넣기
            cur = board[r][c]
            board[r][c] = before

            # before update
            before = cur
        curDir += 1

    board[airLoc[0]][airLoc[1]] = 0


# 공기청정기 위치 알기
temp = []
for r in range(R):
    if board[r][0] == -1:
        temp.append(r)
        board[r][0] = 0
airTop, airDown = (temp[0],0), (temp[1],0)

# 1초 ~ T초 반복
for t in range(T):
    # 1. 미세먼지가 있는 모든 칸에서의 확산
    board = spreadDust(airTop, airDown, board)

    # 2. 공기청정기 작동
    # 2-1. 위쪽은 반시계 방향으로 -> 우, 상, 좌, 하
    airTopDir = [(0,1),(-1,0),(0,-1),(1,0)]
    workAirPurifier(airTop, airTopDir)

    # 2-2. 아래쪽은 시계 방향으로 -> 우, 하, 좌, 상
    airDownDir = [(0,1),(1,0),(0,-1),(-1,0)]
    workAirPurifier(airDown, airDownDir)

# 총 미세먼지 양 구하기
answer = 0
for b in board:
    answer += sum(b)
print(answer)