이 문제로 골4가 되었습니당 ~ ㅋ
r*c 크기의 집에 공기청정기를 설치하려고 한다. 공청기는 항상 1번 열에 설치되고, 세로로 두자리를 차지한다. 는 (r,c)칸의 미세먼지 양을 의미한다. 공청기 위치를 제외한 모든 칸에 부여된다.
1초간 다음과 같은 일이 일어난다.
문제 읽으면서 쉽네,, 했는데 처음에 설계를 잘못해서 디버깅하는데 꽤 걸렸다 ^_ㅠ
미세먼지가 확산되는 부분은 다음과 같이 구현했다.
# 해당 시간동안의 각 칸 확산량을 저장하는 리스트
check_room = [[0 for _ in range(C)] for _ in range(R)]
# 1. 미세먼지 확산
for i in range(R):
for j in range(C):
if room[i][j] > 0:
# 미세먼지 있으면
if room[i][j] >= 5:
count = 0
for d in range(4):
# 확산 가능한 네방향 체크
ni, nj = i+dx[d], j+dy[d]
if in_range(ni, nj) and room[ni][nj] != -1:
check_room[ni][nj] += room[i][j]//5
count += 1
room[i][j] -= (room[i][j]//5)*count
for i in range(R):
for j in range(C):
room[i][j] += check_room[i][j]
1초동안 모든 칸에서 확산이 일어나는데 (0,0)부터 먼저 계산해서 더해줘버리면 이후의 결과에 영향을 미친다. 확산량을 새로운 리스트에 저장해서 다 확산된 후 결과를 더해줘야 한다.
공청기로 순환되는 부분은 다음과 같은 로직으로 구현하였다.
우선 dx, dy는 dx = [-1, 1, 0, 0], dy = [0, 0, -1, 1]
으로 상-하-좌-우 순서이다. 두칸을 차지하는 공청기에서 윗칸을 공청기1, 아랫칸을 공청기2라고 했을때, 아래 그림에서 공청기1 기준으로 반시계방향으로 미는 부분을 생각해보자.
공청기1의 순환에서 공청기 방향으로 들어오는 맨 끝칸부터 차례대로 옮긴다. 기준 칸을 (x,y), 다음 칸을 x+dx[d],y+dy[d]인 (nx,ny)라고 했을때, room[x][y] <- room[nx][ny]
로 먼지를 옮기고, x,y <- nx, ny
로 갱신해 준다.
만약, nx, ny가 방의 범위를 벗어난 경우는 다음과 같이 경우를 나눠 nx,ny, 그리고 방향을 갱신했다.
공청기 2도 똑같이 경우를 나눠서 구현하면 된다.
코드는 다음과 같다.
# 2. 공청기 가동
for a in range(2):
# 시계방향으로 확산시키기
x, y, d = aircleaner[a][0]+dx[a], aircleaner[a][1], a
while True:
nx, ny = x+dx[d], y+dy[d]
if (nx, ny) == aircleaner[a]:
room[x][y] = 0
break
if a == 0:
# 시계방향 확산일때
if nx < 0:
nx, ny = x, y+1
d = 3
elif nx > aircleaner[a][0]:
nx, ny = x, y-1
d = 2
elif ny >= C:
nx, ny = x+1, y
d = 1
elif a == 1:
if nx >= R:
nx, ny = x, y+1
d = 3
elif nx < aircleaner[a][0]:
nx, ny = x, y-1
d = 2
elif ny >= C:
nx, ny = x-1, y
d = 0
room[x][y] = room[nx][ny]
x, y = nx, ny
import sys
input = sys.stdin.readline
# 상 하 좌 우
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def in_range(x, y):
if x in range(R) and y in range(C):
return True
return False
R, C, T = map(int, input().split())
room = []
aircleaner = []
for i in range(R):
tmp = list(map(int, input().split()))
for j in range(C):
if tmp[j] == -1:
# 공청기 위치 기록
aircleaner.append((i,j))
room.append(tmp)
for time in range(T):
check_room = [[0 for _ in range(C)] for _ in range(R)]
# 1. 미세먼지 확산
for i in range(R):
for j in range(C):
if room[i][j] > 0:
# 미세먼지 있으면
if room[i][j] >= 5:
count = 0
for d in range(4):
# 확산 가능한 네방향 체크
ni, nj = i+dx[d], j+dy[d]
if in_range(ni, nj) and room[ni][nj] != -1:
check_room[ni][nj] += room[i][j]//5
count += 1
room[i][j] -= (room[i][j]//5)*count
for i in range(R):
for j in range(C):
room[i][j] += check_room[i][j]
# 2. 공청기 가동
for a in range(2):
# 시계방향으로 확산시키기
x, y, d = aircleaner[a][0]+dx[a], aircleaner[a][1], a
while True:
nx, ny = x+dx[d], y+dy[d]
if (nx, ny) == aircleaner[a]:
room[x][y] = 0
break
if a == 0:
# 시계방향 확산일때
if nx < 0:
nx, ny = x, y+1
d = 3
elif nx > aircleaner[a][0]:
nx, ny = x, y-1
d = 2
elif ny >= C:
nx, ny = x+1, y
d = 1
elif a == 1:
if nx >= R:
nx, ny = x, y+1
d = 3
elif nx < aircleaner[a][0]:
nx, ny = x, y-1
d = 2
elif ny >= C:
nx, ny = x-1, y
d = 0
room[x][y] = room[nx][ny]
x, y = nx, ny
answer = 0
for r in room:
answer += sum(r)
print(answer + 2)
시키는 대로 하면 되는 이런 문제는 금방금방 풀어야 될 것 같은데 마음같지 않으네요 ,,,,, 코드로 옮기기 전에 수도코드를 얼마나 자세히 작성해야 효율적일지 아직 모르겠슴