문제
집을 크기가 RxC인 격자판으로 나타냈고 1x1크기의 칸으로 나눴다.
각 칸에는 미세먼지 양이 적혀있고, 공기청정기는 항상 1번 열에 설치되어있으며 두 칸을 차지한다. 그리고 1초 동안 다음과 같은 일이 순서대로 일어난다.
1. 미세먼지가 확산된다. 확산은 모든 칸에서 동시에 일어난다.
- 미세먼지는 인접한 네 방향으로 확산된다.
- 인접한 방향에 공기청정기가 있거나 칸이 없으면 그 방향으로는 확산이 일어나지 않는다.
- 확산되는 양은 해당 칸의 미세먼지양/5이다.
- 확산되고 남은 미세먼지의 양은 원래 미세먼지양 - (미세먼지양/5 * 확산된 방향의 수)이다.
2. 공기청정기가 작동한다.
- 공기청정기에서 바람이 나온다.
- 위쪽 공기청정기의 바람은 반시계 방향으로 순환하고 아래쪽 공기청정기의 바람은 시계방향으로 순환한다.
- 바람이 불면 미세먼지가 바람의 방향대로 모두 한 칸씩 이동한다.
- 공기청정기로 들어간 미세먼지는 모두 정화된다.
T초가 지난 후의 남아있는 미세먼지의 양을 구하라
입력
첫째 줄에 R, C, T가 주어진다.
둘째 줄부터 공기청정기의 위치정보와 미세먼지양이 담긴 맵을 입력한다.
공기청정기가 설치된 곳은 -1이고 윗 행, 아랫행과 두 칸이상 떨어져 있다.
출력
첫째 줄에 T초가 지난 후 남아있는 미세먼지의 양을 출력한다.
문제에서 주어진 조건대로 구현을 하였다.
이때 크게 미세먼지의 확산과 공기청정기의 순환으로 나누어서 진행할 수 있다.
하지만 pypy3로 제출하여 통과되었고 최적화 과정을 진행한 후에 python3로 제출을 해야겠다.
구현
미세먼지를 확산하는 부분이다.
전달받은 현재위치에서 확산이 가능한 부분을 체크하여 확산을 진행하고 0으로 초기화된 맵에 확산된 미세먼지양을 추가한다. 이는 나중에 원본 맵에 더해질 것이다.
그리고 확산이 된 부분만큼 원본 맵에서 메시먼지 양을 줄인다.
def spread(y, x):
global temp
cnt = 0
dy = [1, -1, 0, 0]
dx = [0, 0, 1, -1]
for d in range(4):
ny = y + dy[d]
nx = x + dx[d]
if check_range(ny, nx) and matrix[ny][nx] != -1:
cnt += 1
temp[ny][nx] += matrix[y][x]//5
matrix[y][x] -= (matrix[y][x]//5 * cnt)
공기청정기의 윗부분과 아랫부분의 바람 이동을 나타낸 것이다.
문제에서 주어진 바람의 방향이 아닌 반대로 미세먼지를 끌어당기도록 구현하였다.
끌어당기는 방향이 규칙이 있으니 방향을 위한 델타함수를 그 규칙에 맞게 설정하고 어떠한 조건에 따라 방향을 바꾸는 코드가 더 괜찮을 것 같다.
def top_cycle(y, x):
# 아래에서 위
for i in range(y, 0, -1):
if i == y:
matrix[y-1][0] = 0
else:
matrix[i][0] = matrix[i-1][0]
# 왼쪽에서 오른쪽
for i in range(0, C-1):
matrix[0][i] = matrix[0][i+1]
# 위에서 아래
for i in range(0, y):
matrix[i][C-1] = matrix[i+1][C-1]
# 오른쪽에서 왼쪽
for i in range(C-1, 1, -1):
matrix[y][i] = matrix[y][i-1]
matrix[y][1] = 0
def bottom_cycle(y, x):
# 위에서 아래로
for i in range(y, R-1):
if i == y:
matrix[i+1][0] = 0
else:
matrix[i][0] = matrix[i+1][0]
# 왼쪽에서 오른쪽
for i in range(C-1):
matrix[R-1][i] = matrix[R-1][i+1]
# 아래에서 위로
for i in range(R-1, y, -1):
matrix[i][C-1] = matrix[i-1][C-1]
# 오른쪽에서 왼쪽
for i in range(C-1, 1, -1):
matrix[y][i] = matrix[y][i-1]
matrix[y][1] = 0전체 코드
import sys
input = sys.stdin.readline
def check_range(y, x):
return (y>=0 and y<R) and (x>=0 and x<C)
def spread(y, x):
global temp
cnt = 0
dy = [1, -1, 0, 0]
dx = [0, 0, 1, -1]
for d in range(4):
ny = y + dy[d]
nx = x + dx[d]
if check_range(ny, nx) and matrix[ny][nx] != -1:
cnt += 1
temp[ny][nx] += matrix[y][x]//5
matrix[y][x] -= (matrix[y][x]//5 * cnt)
def top_cycle(y, x):
# 아래에서 위
for i in range(y, 0, -1):
if i == y:
matrix[y-1][0] = 0
else:
matrix[i][0] = matrix[i-1][0]
# 왼쪽에서 오른쪽
for i in range(0, C-1):
matrix[0][i] = matrix[0][i+1]
# 위에서 아래
for i in range(0, y):
matrix[i][C-1] = matrix[i+1][C-1]
# 오른쪽에서 왼쪽
for i in range(C-1, 1, -1):
matrix[y][i] = matrix[y][i-1]
matrix[y][1] = 0
def bottom_cycle(y, x):
# 위에서 아래로
for i in range(y, R-1):
if i == y:
matrix[i+1][0] = 0
else:
matrix[i][0] = matrix[i+1][0]
# 왼쪽에서 오른쪽
for i in range(C-1):
matrix[R-1][i] = matrix[R-1][i+1]
# 아래에서 위로
for i in range(R-1, y, -1):
matrix[i][C-1] = matrix[i-1][C-1]
# 오른쪽에서 왼쪽
for i in range(C-1, 1, -1):
matrix[y][i] = matrix[y][i-1]
matrix[y][1] = 0
R, C, T = map(int, input().split())
matrix = [list(map(int, input().split())) for _ in range(R)]
air = []
for y in range(R):
if matrix[y][0] == -1:
air.append((y, 0))
while T:
temp = [[0 for _ in range(C)] for _ in range(R)]
# 확산
for y in range(R):
for x in range(C):
if matrix[y][x] > 0 :
spread(y, x)
# 확산 후 확산된 미세먼지 더하기
for y in range(R):
for x in range(C):
matrix[y][x] += temp[y][x]
# 순환
top_cycle(air[0][0], air[0][1])
bottom_cycle(air[1][0], air[1][1])
T -= 1
answer = 0
for y in range(R):
for x in range(C):
if matrix[y][x] > 0:
answer += matrix[y][x]
print(answer)'알고리즘 풀이 > 백준' 카테고리의 다른 글
| [백준 1436] 영화감독 숌 (0) | 2021.03.02 |
|---|---|
| [백준 17779] 게리멘더링 2 (0) | 2021.02.25 |
| [백준 2947] 나무 조각 (0) | 2021.02.24 |
| [백준 1244] 스위치 켜고 끄기 (0) | 2021.02.24 |
| [백준 2407] 조합 (0) | 2021.02.23 |