[BOJ] 17144 - 미세먼지 안녕!
이 문제로 골4가 되었습니당 ~ ㅋ
문제 링크
문제 설명
r*c 크기의 집에 공기청정기를 설치하려고 한다. 공청기는 항상 1번 열에 설치되고, 세로로 두자리를 차지한다. 는 (r,c)칸의 미세먼지 양을 의미한다. 공청기 위치를 제외한 모든 칸에 부여된다.
1초간 다음과 같은 일이 일어난다.
- 미세먼지의 확산
: (r,c)의 인접한 4방향으로 //5만큼의 미세먼지가 확산
-> 벽이거나 공청기면 해당 칸으로는 확산 x
-> = - (//5)*(확산 칸의 수) - 공청기 작동
- 바람은 공청기의 윗칸 (x,1)은 반시계 방향으로 순환, 아래칸 (x+1,1)은 시계 방향으로 순환한다.
- 이 방향대로 먼지가 한칸씩 이동하고, 공청기로 들어간 미세먼지는 정화된다.
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]
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)
시키는 대로 하면 되는 이런 문제는 금방금방 풀어야 될 것 같은데 마음같지 않으네요 ,,,,, 코드로 옮기기 전에 수도코드를 얼마나 자세히 작성해야 효율적일지 아직 모르겠슴
Author And Source
이 문제에 관하여([BOJ] 17144 - 미세먼지 안녕!), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@woo0_hooo/BOJ-17144-미세먼지-안녕저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)