https://www.acmicpc.net/problem/17144
문제
미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 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)×(확산된 방향의 개수) 이다.
공기청정기가 작동한다.
공기청정기에서는 바람이 나온다.
위쪽 공기청정기의 바람은 반시계방향으로 순환하고, 아래쪽 공기청정기의 바람은 시계방향으로 순환한다.
바람이 불면 미세먼지가 바람의 방향대로 모두 한 칸씩 이동한다.
공기청정기에서 부는 바람은 미세먼지가 없는 바람이고, 공기청정기로 들어간 미세먼지는 모두 정화된다.
입력
첫째 줄에 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초가 지난 후 구사과 방에 남아있는 미세먼지의 양을 출력한다.
예제 입력 1
0 0 0 0 0 0 0 9
0 0 0 0 3 0 0 8
-1 0 5 0 0 0 22 0
-1 8 0 0 0 0 0 0
0 0 0 0 0 10 43 0
0 0 5 0 15 0 0 0
0 0 40 0 0 0 20 0예제 출력 1
188
풀이
풀이과정을 (1) 미세먼지의 확산 (2) 공기 청정기 바람으로 인한 먼지의 이동, 2갈래로 나누어 생각했다.
사전에 생각할 것
공기청정기: -1로 총 두 칸에 위치 고정
- 위,아래 위치에 따라 바람의 방향(반시계/시계)로 나누어짐
- 바람이 닿지 않는 공간이 있음
미세먼지: 1초마다 상하좌우 확산, 공청기, 배열 범위 밖에서는 확산 x
- 확산 양: A - (A/5) * 확산된 칸 수
- A가 5보다 작으면 계산된 값이 0이므로 이동 x정답 코드
import sys
input = sys.stdin.readline
r, c, t = map(int, input().split()) # 행, 열, 시간
arr = [list(map(int, input().split())) for _ in range(r)]
air_cleaner = []
cnt = 0
for x in range(r):
if arr[x][0] == -1:
air_cleaner.append((x, cnt))
cnt += 1
if cnt == 2:
break
d = [(0, 1), (0, -1), (1, 0), (-1, 0)] # 4방향 확산
up = [(0, 1), (-1, 0), (0, -1), (1, 0)]
down = [(0, 1), (1, 0), (0, -1), (-1, 0)]
def wind(start, loc):
x, y = start, 1
idx = 0
previous = 0 # 이전값
if loc == 0: # up
while True:
nx = x + up[idx][0]
ny = y + up[idx][1]
# 공기청정기에 도달하면 while문 종료
if x == start and y == 0:
break
# 제한 범위 바깥이면 idx +1
if nx < 0 or nx >= r or ny < 0 or ny >= c:
idx += 1
continue
# 변수값 바꾸기 (swap)
arr[x][y], previous = previous, arr[x][y]
x, y = nx, ny
return # while문 다 돌았으면 종료
elif loc == 1: # up
while True:
nx = x + down[idx][0]
ny = y + down[idx][1]
# 공기청정기에 도달하면 while문 종료
if x == start and y == 0:
break
# 제한 범위 바깥이면 idx +1
if nx < 0 or nx >= r or ny < 0 or ny >= c:
idx += 1
continue
# 변수값 바꾸기 (swap)
arr[x][y], previous = previous, arr[x][y]
x, y = nx, ny
while t:# t초동안 돌리기
move = [[0] * c for _ in range(r)]
for x in range(r):
for y in range(c):
if arr[x][y] >= 5: # 5보다 작으면 확산 이동 x
dust = arr[x][y] // 5 # 확산될 양
for i in d:
nx = x + i[0]
ny = y + i[1]
# 범위 밖이거나 공기청정기가 있는 장소면 패스
if nx < 0 or nx >= r or ny < 0 or ny >= c or arr[nx][ny] == -1:
continue
arr[x][y] -= dust
move[nx][ny] += dust
for x in range(r):
for y in range(c):
arr[x][y] += move[x][y]
wind(air_cleaner[0][0], air_cleaner[0][1])
wind(air_cleaner[1][0], air_cleaner[1][1])
t -= 1 # 1초 지났다
total = 0
for x in range(r):
total += sum(arr[x])
print(total+2) 1. 공기청정기 위치 저장
air_cleaner = [] # 0번째 값이 위, 1번째 값이 아래
cnt = 0
for x in range(r):
if arr[x][0] == -1:
# 행의 위치, cnt 표기
air_cleaner.append((x, cnt))
cnt += 1
if cnt == 2:
break- 공기 청정기는 1번 열(인덱스 상, 0)에만 설치되므로 arr[x][0]을 확인하며 공기청정기(-1) 행의 위치를 찾는다.
- cnt변수로 2개를 찾았으면 for문을 불필요하게 더 보지 않고 종료하도록 하고, 변수는 추후 공기 청정기 위, 아래를 구별하기 위한 값으로 활용한다.
2. 미세먼지 확산
d = [(0, 1), (0, -1), (1, 0), (-1, 0)] # 4방향 확산
while t:
move = [[0] * c for _ in range(r)]
for x in range(r):
for y in range(c):
if arr[x][y] >= 5: # 5보다 작으면 확산 이동 x
dust = arr[x][y] // 5 # 확산될 양
for i in d:
nx = x + i[0]
ny = y + i[1]
# 범위 밖이거나 공기청정기가 있는 장소면 패스
if nx < 0 or nx >= r or ny < 0 or ny >= c or arr[nx][ny] == -1:
continue
arr[x][y] -= dust
move[nx][ny] += dust
# 이동한 먼지양들 배열에 더해줌
# 변수 할당(갱신)이 아니라 더해주는 이유: 원래 있던 값에서 빠진 dust양 계산을 위해서다
for x in range(r):
for y in range(c):
arr[x][y] += move[x][y]- t초 동안 필요한 조건에 따른 작업을 수행하기 위해 while문 사용 (for _ in range(t)를 사용해도 될 것)
- 미세먼지를 델타 탐색을 통해 확산시킨다.
- 미세먼지 양을 원래 배열에서 바로 갱신하면 동시간대의 모든 먼지의 이동양을 정확하게 계산할 수 없으므로 move 배열을 만들어 이용한다.
- move 배열을 매 초마다 갱신야 이전에 이동된 먼지양이 누적되어 계산되지 않는다.
3. 공기청정기 바람 돌리기
위: 시작 기준으로 벽을 만날 때까지 우, 상, 좌, 하
아래: 시작 기준으로 벽을 만날때까지 우, 하, 좌, 상
공기 청정기가 놓인 위치에 닿은 먼지는 제거, 다다르면 바람 종료 up = [(0, 1), (-1, 0), (0, -1), (1, 0)]
down = [(0, 1), (1, 0), (0, -1), (-1, 0)]
# start: 공기청정기가 위치한 행의 인덱스 번호
# loc: 공기청정기 위, 아래 구분
# 위는 0, 아래는 1
def wind(start, loc):
x, y = start, 1
idx = 0
previous = 0 # 이전값
if loc == 0: # up
while True:
nx = x + up[idx][0]
ny = y + up[idx][1]
# 공기청정기에 도달하면 while문 종료
if x == start and y == 0:
break
# 제한 범위 바깥이면 idx +1
if nx < 0 or nx >= r or ny < 0 or ny >= c:
idx += 1
continue
# 변수값 바꾸기 (swap)
arr[x][y], previous = previous, arr[x][y]
x, y = nx, ny
return # while문 다 돌았으면 종료
elif loc == 1: # up
while True:
nx = x + down[idx][0]
ny = y + down[idx][1]
# 공기청정기에 도달하면 while문 종료
if x == start and y == 0:
break
# 제한 범위 바깥이면 idx +1
if nx < 0 or nx >= r or ny < 0 or ny >= c:
idx += 1
continue
# 변수값 바꾸기 (swap)
arr[x][y], previous = previous, arr[x][y]
x, y = nx, ny- for문으로 각 방향에 맞는 이동을 만들어줘도 된다.
- 나는 while문에서 idx를 범위에 맞게 바꿔가며 이동하게 했다.
이하, 잘못된 구현 코드
- 공기청정기 작동 면에서 구현을 실패했던 코드다.
def wind(start, loc):
global arr
x, y, i = start, 1, 0
tmp = [[0] * c for _ in range(r)]
if loc == 0: # up
while True:
nx = x + up[i][0]
ny = y + up[i][1]
if i == 3 and arr[nx][ny] == -1:
tmp[x][y] = 0
tmp[nx][ny] = -1
# 상단 부분만 가져오도록 해야함
for l in range(start+1):
for m in range(c):
arr[l][m] = tmp[l][m]
return
if 0 <= nx < r and 0 <= ny < c:
if arr[x][y] != -1:
tmp[nx][ny] = arr[x][y]
x, y = nx, ny
else: # 범위 밖이면
i += 1
elif loc == 1: # down
while True:
nx = x + down[i][0]
ny = y + down[i][1]
if i==3 and nx == start and ny == 0:
tmp[x][y] = 0
tmp[nx][ny] = -1
# 하단 부분만 가져오도록 해야함
for l in range(start+1, r):
for m in range(c):
arr[l][m] = tmp[l][m]
return
if 0 <= nx < r and 0 <= ny < c:
if arr[x][y] != -1:
tmp[nx][ny] = arr[x][y]
x, y = nx, ny
else: # 범위 밖이면
i += 1- 공기청정기 바람 이동 영역이 상 하로 나누어져 있는데 처음에 한 배열을 그대로 넣어서 사용해 상단 부분 이동 후, 하단은 다 0의 값을 갖게 되는 오류가 났다.
- 이를 해결하기 위해 for문에서 range로 상단과 하단 부분을 분리했지만, 공기청정기 바람은 한 줄씩 이동하고 가운데 공간은 영향을 주지 않는 점을 간과했다.
- 또한 값을 넣을 때도 swap 대신 다음 위치에 현재 값을 할당하고, 현재 값을 0으로 할당하는 식으로 값을 갱신해서 오류가 났다.
