📩 출처
문제
미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사과는 뛰어난 코딩 실력을 이용해 각 칸 (r, c)에 있는 미세먼지의 양을 실시간으로 모니터링하는 시스템을 개발했다. (r, c)는 r행 c열을 의미한다.
공기청정기는 항상 1번 열에 설치되어 있고, 크기는 두 행을 차지한다. 공기청정기가 설치되어 있지 않은 칸에는 미세먼지가 있고, (r, c)에 있는 미세먼지의 양은 Ar,c이다.
1초 동안 아래 적힌 일이 순서대로 일어난다.
- 미세먼지가 확산된다. 확산은 미세먼지가 있는 모든 칸에서 동시에 일어난다.
- (r, c)에 있는 미세먼지는 인접한 네 방향으로 확산된다.
- 인접한 방향에 공기청정기가 있거나, 칸이 없으면 그 방향으로는 확산이 일어나지 않는다.
- 확산되는 양은 Ar,c/5이고 소수점은 버린다.
- (r, c)에 남은 미세먼지의 양은 Ar,c - (Ar,c/5)×(확산된 방향의 개수) 이다.
- 공기청정기가 작동한다.
- 공기청정기에서는 바람이 나온다.
- 위쪽 공기청정기의 바람은 반시계방향으로 순환하고, 아래쪽 공기청정기의 바람은 시계방향으로 순환한다.
- 바람이 불면 미세먼지가 바람의 방향대로 모두 한 칸씩 이동한다.
- 공기청정기에서 부는 바람은 미세먼지가 없는 바람이고, 공기청정기로 들어간 미세먼지는 모두 정화된다.
다음은 확산의 예시이다.
공기청정기의 바람은 다음과 같은 방향으로 순환한다.
방의 정보가 주어졌을 때 T초가 지난 후 구사과의 방에 남아있는 미세먼지의 양을 구해보자.
입력
첫째 줄에 R, C, T (6 ≤ R, C ≤ 50, 1 ≤ T ≤ 1,000) 가 주어진다.
둘째 줄부터 R개의 줄에 Ar,c (-1 ≤ Ar,c ≤ 1,000)가 주어진다. 공기청정기가 설치된 곳은 Ar,c가 -1이고, 나머지 값은 미세먼지의 양이다. -1은 2번 위아래로 붙어져 있고, 가장 윗 행, 아랫 행과 두 칸이상 떨어져 있다.
출력
첫째 줄에 T초가 지난 후 구사과 방에 남아있는 미세먼지의 양을 출력한다.
👉 생각
- 먼저 미세먼지가 확산하는 함수 bfs를 만든다. bfs 문제일 것 같아서 이름을 bfs로 지었는데 상관없다.. 그리고 처음에 주어지는 r과 c로 이차원 배열 visited를 만든다.
- t초만큼 for문을 돌려서 한 번마다 미세먼지를 확산시키고 공기청정기를 통해 밀어버린다. 이때 arr을 건드리는게 아니라 t초마다 visited를 생성해서 arr을 기준으로 확산한 것을 visited에 반영하고 visited에서 먼지들을 밀어버린다. 이후 arr을 visted가 참조하는 배열을 참조하도록 하고 visited를 새로 생성한다.
- t초 만큼 반복하면 arr의 현재 미세먼지의 상태가 기록되어 있다. 그런데 이 코드는 파이썬은 시간초과가 발생하고 pypy로 통과를 했다. 아무래도 t초마다 visited를 생성해서 그런 것 같은 느낌...? 지금 기차에서 하느라 베터리가 없어서... 파이썬으로 통과하는 코드는 조금 더 생각해 봐야할 것 같다.
from collections import deque
def bfs(x, y):
q = deque([])
q.append((x, y))
while q:
x, y = q.popleft()
tmp = 0
for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
nx, ny = x + dx, y + dy
if 0 <= nx < r and 0 <= ny < c and arr[nx][ny] >= 0:
tmp += arr[x][y] // 5
visited[nx][ny] += arr[x][y] // 5
visited[x][y] += arr[x][y] - tmp
r, c, t = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(r)]
for i in range(r):
if arr[i][0] == -1:
up = i
down = i + 1
break
cnt = 0
for _ in range(t):
visited = [[0] * c for _ in range(r)]
cnt += 1
# 미세먼지 확산
for i in range(r):
for j in range(c):
if arr[i][j] > 0:
bfs(i, j)
tmp1, tmp2 = visited[up][-1], visited[down][-1]
for i in range(c - 1, 1, -1):
visited[up][i] = visited[up][i - 1]
visited[down][i] = visited[down][i - 1]
visited[up][1], visited[down][1] = 0, 0
# 공기청정기 바람 방향 위로
tmp3, tmp4 = visited[0][-1], visited[-1][-1]
for i in range(up - 1):
visited[i][-1] = visited[i + 1][-1]
visited[up - 1][-1] = tmp1
for i in range(r - 1, down + 1, -1):
visited[i][-1] = visited[i - 1][-1]
visited[down + 1][-1] = tmp2
# 공기청정기 바람 방향 <-
tmp5, tmp6 = visited[0][0], visited[-1][0]
for i in range(c - 2):
visited[0][i] = visited[0][i + 1]
visited[-1][i] = visited[-1][i + 1]
visited[0][-2] = tmp3
visited[-1][-2] = tmp4
# 공기청정기 바람 방향 아래
for i in range(up - 1, 1, -1):
visited[i][0] = visited[i - 1][0]
visited[1][0] = tmp5
for i in range(down + 1, r - 2):
visited[i][0] = visited[i + 1][0]
visited[-2][0] = tmp6
visited[up][0] = -1
visited[down][0] = -1
arr = visited
result = 0
for i in range(r):
for j in range(c):
result += arr[i][j]
print(result+2)