17144번: 미세먼지 안녕!
미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사
www.acmicpc.net
전형적인 구현 및 시뮬레이션 문제이다.
구현 및 시뮬레이션 문제를 풀 때는, (사실 모든 문제가 마찬가지지만) 주어진 조건을 잘 파악하여야 한다. 그리고 중복되는 부분이나 자주 호출되는 부분이 있는지 확인해보고, 예외 상황 등을 파악한다.
그리고 모듈화 (함수나 클래스 등으로 코드의 일정 단위를 묶어주는 등)를 잘해주어야 한다.
보통 이런 격자구조가 나오면 기본적으로 좌, 우, 위, 아래 탐색을 해주는 BFS/DFS가 기본이다. 이 문제에서는 각 칸에 있는 미세먼지 4방향으로 퍼져나가게 되는데, BFS/DFS 등을 돌면서 퍼져나간 값을 해당 이웃 칸에 순서대로 중첩해주면 다음 그 칸에서 미세먼지가 퍼질 때 오류가 있을 수 있다. 원래 갖고 있던 미세먼지보다 많아졌을 테니 말이다. 따라서 필자는 각 칸에 숫자를 2개 담을 수 있게 하였다.
각 칸에 들어가는 값의 자료구조: [원래 갖고 있는 미세먼지, 이웃 칸에서 온 미세먼지]
원래 갖고 있는 미세먼지는 건드리지 않고, 이웃에서 온 미세먼지만 계속 중첩해준다. 그리고 그 값을 마지막에 원래 갖고 있는 미세먼지에 모아두는 식으로 '미세먼지의 확산'을 표현하였다.
다음은 순환이다.
공기청정기는 항상 왼쪽 끝에 붙어있고, 바람은 오른쪽 벽끝까지갔다가 쭉 훑어서 돌아온다.
여기서도 주의할 부분은 미세먼지가 순환되어가는 방향대로 전파를 하면, 다음 칸에 이전 칸 값이 덮어 쓰여 원래 자신의 값을 잃어버리게 된다.
위와 같이, 2가 오른쪽으로 가면서 3을 덮어서, 두 번째칸에서 세 번째 칸으로 넘어가는 값이 3이 아니라 2가 되게 된다.
그래서 필자는 바람의 방향대로 앞에서부터 (위의 그림에서부터 좌측 첫 번째 칸) 값을 이동시키는 게 아니라, 가장 뒤에서부터 (위의 그림에서는 가장 우측 칸) 앞의 값을 끌어왔다.
그리고 마지막은 T초후의 미세먼지 총량이다. 필자는 그냥 칸 전체를 모두 확인해서 카운트하였다.
이제 위에 그동안 언급한 내용들을 묶어보면,
(확산) - (순환) - (카운트)의 과정이 계속 반복되는 것으로 정리될 수 있다.
확산 시에는 몫을 취할 때, 자연수로 받아야 한다는 점, 순환 시에 인덱스에 유의해야 하는 점, 카운트 시에 공기청정기에 -1이 들어있다는 점 등에 유의하면 된다
<주요 내용>
BFS, 구현, 시뮬레이션
<코드>
큐, 스택, 덱 등 매우 자주 사용되는 deque모듈이다.
from collections import deque
import sys
si = sys.stdin.readline
dust_q, board, now, cleaner1 = deque(), [], 0, 0
r, c, t = [int(e) for e in si().split()]
for i in range(r):
row = [[int(e), 0] for e in si().split()]
for j in range(c):
if row[j][0] > 0:
dust_q.append((i, j))
elif row[j][0] == -1 and not cleaner1:
cleaner1 = i
cleaner2 = i+1
board.append(row)
def spread(r, c):
global dust_q, board
dr, dc = [0, 1, 0, -1], [1, 0, -1, 0]
while dust_q:
curr = dust_q.popleft()
cr, cc, acc = curr[0], curr[1], 0
spr = board[cr][cc][0]//5
for i in range(4):
nr, nc = cr+dr[i], cc+dc[i]
if 0 <= nr < r and 0 <= nc < c and board[nr][nc][0] != -1:
board[nr][nc][1] += spr
acc += spr
board[cr][cc][0] -= acc
def settledown(r, c):
global board
for i in range(r):
for j in range(c):
if board[i][j][1]:
board[i][j][0] += board[i][j][1]
board[i][j][1] = 0
def circulate(cleaner1, cleaner2, r, c):
global dust_q, board
for i in range(cleaner1-1, 0, -1):
board[i][0][0] = board[i-1][0][0]
for i in range(c-1):
board[0][i][0] = board[0][i+1][0]
for i in range(cleaner1):
board[i][c-1][0] = board[i+1][c-1][0]
for i in range(c-1, 1, -1):
board[cleaner1][i][0] = board[cleaner1][i-1][0]
board[cleaner1][1][0] = 0
for i in range(cleaner2+1, r-1):
board[i][0][0] = board[i+1][0][0]
for i in range(c-1):
board[r-1][i][0] = board[r-1][i+1][0]
for i in range(r-1, cleaner2, -1):
board[i][c-1][0] = board[i-1][c-1][0]
for i in range(c-1, 1, -1):
board[cleaner2][i][0] = board[cleaner2][i-1][0]
board[cleaner2][1][0] = 0
for i in range(r):
for j in range(c):
if board[i][j][0] > 0:
dust_q.append((i, j))
def totalcount(r, c):
cnt = 2
for i in range(r):
for j in range(c):
cnt += board[i][j][0]
return cnt
while now != t:
now += 1
spread(r, c)
settledown(r, c)
circulate(cleaner1, cleaner2, r, c)
print(totalcount(r, c))
