[백준] 17144 - 미세먼지 안녕! (G4)

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

17144번: 미세먼지 안녕!

어렵지 않은 구현 & 시뮬레이션 문제.

꼼꼼하게 구현만 하면 풀 수 있다.

판의 사이즈가 크지 않기 때문에 문제에서 시키는 그대로 알고리즘을 짜서 돌리고,

그 결과값을 출력하면 된다.

 

이 문제를 풀 때는 2가지만 떠올리면 되었다.

 

1. 어떻게 확산을 겹치지 않게 시킬 수 있을지

2. 공기청정기의 확산을 어떻게 구현할 것인지

---

<1> 어떻게 확산을 겹치지 않게 시킬 수 있을지

---

가령, 문제의 조건과는 맞지 않지만 단순화해서 5 9 1 과 같은 입력이 있다고 할 때

실제로는 5에서 1의 확산, 9에서 양쪽으로 1의 확산, 1에서 확산이 없어야 한다.

하지만 구현을 잘못하는 경우, 5에서 확산된 결과를 바로 9에 반영해서 10이 되고,

10이된 상태에서 확산을 해서 양쪽으로 2를 보내버리는 문제가 있을 수 있다.

 

나는 단순하게 이 문제를 저장 구조를 분리하여 해결했다.

판사이즈가 50 * 50으로 매우 작은편이기 때문에, 한 칸을 (기존값, 다른 칸에서 확산된 값) 으로 구분하여 저장하고

확산이 모두 끝나면, 다른 값에서 확산된 값을 기존값에 더해주는 식으로 구현했다.

---

<2> 공기청정기의 확산을 어떻게 구현할 것인지

---

난 이 부분에서 시간을 조금 썼다. 배열 내에서 로테이션을 구현하는 경험을 많이 해보지 않았기 때문이다.

처음에는 C언어를 처음 배울 때 지겹게 많이 했던 swap을 이용해서 해보는 것을 생각하다가 막혔었다.

그래서 고민끝에 그냥 단순하게 큐를 사용했다.

 

현재 칸의 값을 큐에 push 하고

큐에서 값을 pop 해서( = 이전 칸의 값) 현재 칸에 넣어주고

 

이걸 공기청정기의 흐름방향을 따라가며 반복해주었다.

 

---

제출 코드

---

import sys
from collections import deque
input = sys.stdin.readline
dr = [0, 0, 1, -1]
dc = [1, -1, 0, 0]
def PrintBoard():
    for i in range(r):
        print(board[i])
    print()
TEST_MODE = False

r, c, t = map(int, input().split())
cleaner = 0
board = [list(map(int, input().split())) for _ in range(r)]

for i in range(r):
    for j in range(c):
        board[i][j] = [board[i][j], 0]

# 공기청정기 위치 찾기 (위쪽만 알면 아래쪽 자동 결정)
for i in range(r):
    if board[i][0][0] == -1:
        cleaner = i
        break

while t > 0:
    if TEST_MODE:
        print("확산전")
        PrintBoard()
    # 확산
    for i in range(r):
        for j in range(c):
            if board[i][j][0] >= 5:
                value = board[i][j][0] // 5
                for k in range(4):
                    check_i, check_j = i + dr[k], j + dc[k]
                    # 칸이 있고
                    if 0 <= check_i < r and 0 <= check_j < c:
                        # 공기 청정기가 아니면 확산
                        if board[check_i][check_j][0] != -1:
                            board[check_i][check_j][1] += value
                            board[i][j][0] -= value

    # 확산한 결과 합치기
    for i in range(r):
        for j in range(c):
            board[i][j][0] += board[i][j][1]
            board[i][j][1] = 0

    if TEST_MODE:
        print("확산 후")
        PrintBoard()

    # 이동
    # 위 공기청정기
    d = deque()
    d.append(0)
    for j in range(1, c):
        d.append(board[cleaner][j][0])
        board[cleaner][j][0] = d.popleft()

    for i in range(cleaner-1, -1 ,-1):
        d.append(board[i][c-1][0])
        board[i][c-1][0] = d.popleft()

    for j in range(c-2, -1, -1):
        d.append(board[0][j][0])
        board[0][j][0] = d.popleft()

    for i in range(1, cleaner):
        d.append(board[i][0][0])
        board[i][0][0] = d.popleft()

    # 아래 공기 청정기
    d = deque()
    d.append(0)
    for j in range(1, c):
        d.append(board[cleaner+1][j][0])
        board[cleaner+1][j][0] = d.popleft()

    for i in range(cleaner+2, r):
        d.append(board[i][c-1][0])
        board[i][c-1][0] = d.popleft()

    for j in range(c-2, -1, -1):
        d.append(board[r-1][j][0])
        board[r-1][j][0] = d.popleft()

    for i in range(r-2, cleaner+1, -1):
        d.append(board[i][0][0])
        board[i][0][0] = d.popleft()

    if TEST_MODE:
        print("이동 후")
        PrintBoard()

    # 초 카운트
    t -= 1

# 결과 출력
s = 0
for i in range(r):
    for j in range(c):
        s += board[i][j][0]

# 공기 청정기로 -1이 2번 더해진 것 감안한 출력
print(s+2)