조금 더 어려운 시뮬레이션 연습하기 -미세먼지 안녕!-
1. 문제
17144번: 미세먼지 안녕! (acmicpc.net)
17144번: 미세먼지 안녕!
미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사
www.acmicpc.net
맵에 배치된 미세먼지가 조건에 따라 확산하고, 설치된 공기청정기가 미세먼지를 흡수할때, 일정시간이 지난 후 남아있는 미세먼지의 양을 구하는 문제
2. 풀이
역시 제시된 순서에 맞게 성실하게 시뮬레이션 구현하면 되겠다
역시 가장 기본은 미세먼지와 공기청정기의 위치를 찾아야겠지
r,c,t = map(int,stdin.readline().split())
maps = [list(map(int,stdin.readline().split())) for _ in range(r)]
##미세먼지와 공기청정기를 찾는다
dust_dict = {}
air_list = []
for y in range(r):
for x in range(c):
if maps[y][x] >= 1:
dust_dict[(x,y)] = maps[y][x]
elif maps[y][x] == -1:
air_list.append((x,y))
시뮬레이션의 가장 기본 테크닉?이었던 dictionary를 이용했음
미생물 격리나 원자소멸시뮬레이션처럼 서로 합쳐질때 dictionary를 사용하는게 유리했잖아
이 문제도 미세먼지가 확산하면서 서로 합쳐질때를 처리하기 위해 dictionary를 사용하는게 나을 것 같다
미세먼지, 공기청정기 위치를 찾았으면 시뮬레이션을 시작
미세먼지 확산 > 공기청정기 작동 순서로 일어난다니까 정말 자연스럽게 미세먼지 확산부터 시키자
미세먼지 dictionary를 key,value로 순회하면서, 확산되는 양은 일단 1/5로 고정이거든
하지만 확산이 가능한 지점을 검사해야돼
4방향으로 확산할텐데 공기청정기가 있거나, 배열 범위를 벗어나면 확산을 못한대
그리고 확산하고나면, 확산한 수만큼 미세먼지가 줄어드니까 확산한 수도 세어야겠지
delta = [[0,1],[1,0],[0,-1],[-1,0]]
#시뮬레이션 시작
for _ in range(t):
#미세먼지 확산단계
after_dust_dict = {}
for (x,y),dust in dust_dict.items():
diff_count = 0 #확산되는 수
diffusion = dust//5 #확산되는 양
if diffusion != 0: #확산되는 양이 0이면.. 확산이 안일어남
for ni,nj in delta:
dx = x + ni
dy = y + nj
#확산 범위를 벗어나는지, 공기청정기가 있는지
if dx >= 0 and dx <= c-1 and dy >= 0 and dy <= r-1 and maps[dy][dx] != -1:
diff_count += 1 #확산이 일어났고
after_dust_dict[(dx,dy)] = after_dust_dict.get((dx,dy),0) + diffusion
#하나의 미세먼지가 확산이 끝나면 현재 자리에 남아있는 양을 체크함
remain = dust - (diffusion * diff_count)
after_dust_dict[(x,y)] = after_dust_dict.get((x,y),0) + remain
확산을 시킬때 이미 배운 테크닉이지만, after_dust_dict에 옮기라고 했었지??
dust를 순회하면서, after_dust_dict에 옮길건데, 이미 다른 dust에서 해당 지점 dx,dy에 중복되어서 들어가는 경우가 있을 수 있겠지?
그런 경우를 위해
after_dust_dict[(dx,dy)] = after_dust_dict.get((dx,dy),0) + diffusion
이렇게 누적합을 하면서 저장을 해준다
그리고 마찬가지로 하나의 미세먼지가 확산이 끝나면 남아있는 양을 체크해야하는데/...
여기서 놓치기 쉬운게 남아있는 미세먼지 양은 그냥 그대로
#하나의 미세먼지가 확산이 끝나면 현재 자리에 남아있는 양을 체크함
remain = dust - (diffusion * diff_count)
after_dust_dict[(x,y)] = remain
remain만 저장하기 쉽지만... 사실 조금만 생각해보면
다른 지점에서 (x,y)지점으로 확산되는 먼지가 있을 수 있기때문에 계속 누적합을 시켜줘야한다
#하나의 미세먼지가 확산이 끝나면 현재 자리에 남아있는 양을 체크함
remain = dust - (diffusion * diff_count)
after_dust_dict[(x,y)] = after_dust_dict.get((x,y),0) + remain
이제 다음 공기청정기가 문제임
공기청정기의 바람이 이동하면서 어떤식으로 움직여야할까 생각해봤는데
일단 확산한 먼지는 after_dust_dict에 있는데.. 이걸 map에 배치하고 공기청정기로 움직여??
그러자니 너무 비효율적
그냥 조금만 생각해봐도 비효율적임
당연히 after_dust_dict내에서 해결해야돼
그러면 이제 이게 가능하냐의 문제인데..
공기청정기 위,아래로 각각 4방향으로 움직이게 만들면 된다는 점에 주목했다
그래서 먼저 각각을 4단계로 구분하는 delta배열을 만들었다
#공기청정기 단계
air_delta = [[[1,0],[0,-1],[-1,0],[0,1]],[[1,0],[0,1],[-1,0],[0,-1]]]
다음, 내가 map의 위에서부터 아래로 순회했으니까 air_list 0번 원소가 위에 있는 청정기이고
1번 원소가 아래에 있는 청정기겠지
그리고 공기청정기가 돌면서 x좌표는 0번으로 고정되어있으니까, y좌표만 알면 어디까지 돌아야하는지 알수 있잖아
for i in range(2):
x = air_list[i][0]+1
y = air_list[i][1]
air_y = air_list[i][1]
after_dust_dict = air_clean(x,y,air_y,after_dust_dict,0,air_delta[i],i)
반복되는 부분이라 air_clean이라는 함수를 정의해서 사용하기로 했다
그리고 이동시킬 먼지의 좌표는 공기청정기의 x좌표 바로 다음지점부터 시작이니까, x = air_list[i][0]+1로 주었다
어떤식으로 했냐면... 공기청정기 바람이 이동하는 지점의 가능한 좌표를 delta배열을 이용해서 차례대로 순회했다
순회하면서 해당 지점의 먼지는 이제 after_dust_dict에 저장되어있으니까, 여기에 접근해서 air_dust라는 변수에 저장
air_dust라는 변수는 이제 다음 지점으로 이동시킬거다
from sys import stdin
def air_clean(x,y,air_y,after_dust_dict,mode,delta,i):
#움직일 먼지
air_dust = after_dust_dict.get((x,y),0)
이렇게 하면 air_dust가 0이어도 상관없지
(x,y)지점의 먼지를 air_dust에 저장해두었고, 이것을 (dx,dy)로 옮겨야하는데...
delta배열을 이용해서 dx,dy 좌표를 구할 수 있겠지
그러면 dx,dy의 먼지를 temp라는 임시 변수에 저장해두고,
after_dust_dict의 (dx,dy)에 air_dust 값을 저장해두면 (x,y)의 먼지를 (dx,dy)로 옮기는 것이 되겠지
그리고나서 temp는? air_dust로 바꿔줘야 반복이 가능하겠지?
from sys import stdin
def air_clean(x,y,air_y,after_dust_dict,mode,delta,i):
#움직일 먼지
air_dust = after_dust_dict.get((x,y),0)
while 1:
if mode == 0:
while 1:
dx = x + delta[mode][0]
dy = y + delta[mode][1]
temp = after_dust_dict.get((dx,dy),0) #움직여야하는 자리의 먼지를 임시 저장해두고
after_dust_dict[(dx,dy)] = air_dust
air_dust = temp #다음에 움직여야할 먼지 양
x = dx
y = dy
하지만, 계속 x가 1 증가하는 동쪽방향으로만 움직일건가?
x쪽 끝에 왔을때, 더 움직일려고하면 배열 범위를 벗어나겠지... 그런 경우를 고려해서 범위를 벗어나는 경우는 이제
x,y랑 air_dust는 그대로 남겨두고, mode만 0에서 1로 바꿔주고 반복문 탈출하고 mode가 1인 반복문으로 넘어가자
from sys import stdin
def air_clean(x,y,air_y,after_dust_dict,mode,delta,i):
#움직일 먼지
air_dust = after_dust_dict.get((x,y),0)
while 1:
if mode == 0:
while 1:
dx = x + delta[mode][0]
dy = y + delta[mode][1]
if dx <= c-1:
temp = after_dust_dict.get((dx,dy),0) #움직여야하는 자리의 먼지를 임시 저장해두고
after_dust_dict[(dx,dy)] = air_dust
else: ##범위를 벗어나는 경우..
mode = 1 #위쪽으로 움직이도록
break #움직이지 않고
air_dust = temp #다음에 움직여야할 먼지 양
x = dx
y = dy
그러면 이제 mode=1일때도 위와 똑같은 논리로 먼지를 이동시켜주면 되겠다.
범위를 벗어날려고하면 mode=2로 바꾸고 반복문 탈출하고...
elif mode == 1: #위쪽 혹은 아래쪽으로 움직이는 단계
while 1:
dx = x + delta[mode][0]
dy = y + delta[mode][1]
if i == 0:
if dy >= 0:
temp = after_dust_dict.get((dx,dy),0)
after_dust_dict[(dx,dy)] = air_dust
else:
mode = 2
break
else:
if dy <= r-1:
temp = after_dust_dict.get((dx,dy),0)
after_dust_dict[(dx,dy)] = air_dust
else:
mode = 2 #왼쪽으로 움직이는 단계
break
air_dust = temp
x = dx
y = dy
mode=1에서는 위로 움직이는 경우와 아래로 움직이는 경우를 구분해서, 한번에 구현하도록 만들었다
i=0은 위로 움직이는 경우로 dy가 0보다 작으면 범위를 벗어나는 것이고
i=1이면 아래로 움직이는 경우로 dy가 r-1보다 크다면 범위를 벗어나는 것이다
elif mode == 2: #왼쪽으로 움직이는 단계
while 1:
dx = x + delta[mode][0]
dy = y + delta[mode][1]
if dx >= 0:
temp = after_dust_dict.get((dx,dy),0)
after_dust_dict[(dx,dy)] = air_dust
else:
mode = 3
break
air_dust = temp
x = dx
y = dy
mode=2일때는 mode=0과 마찬가지로 위로 움직이는 경우랑, 아래로 움직이는 경우가 서로 똑같이 왼쪽으로 움직이는 경우이므로 굳이 나눌 필요 없다
elif mode == 3: #위쪽 혹은 아래쪽으로 움직이는 단계
while 1:
dx = x + delta[mode][0]
dy = y + delta[mode][1]
if i == 0:
if dy < air_y:
temp = after_dust_dict.get((dx,dy),0)
after_dust_dict[(dx,dy)] = air_dust
elif dy == air_y:
return after_dust_dict
else:
if dy > air_y:
temp = after_dust_dict.get((dx,dy),0)
after_dust_dict[(dx,dy)] = air_dust
elif dy == air_y:
return after_dust_dict
air_dust = temp
x = dx
y = dy
이제 mode=3일때는 공기청정기로 먼지가 하나 흡수되는 단계라서... 미리 구해놓은 target지점인 air_y와 비교하는 작업이 필요하다
(dx,dy)가 돌면서, dy가 air_y와 같아진다면... 그 먼지는 after_dust_dict에 저장할 필요가 없다
없어지는 것이니까
그러면 해당 단계에서는 시뮬레이션이 끝난 것이니까 after_dust_dict를 return하면 되겠다
근데 이렇게까지 왔을때 문제가 되는 부분이 있었다
마지막까지 옮겼을때,, 최초 빨간색 부분은 파란색으로 옮겨가면서.. 옮겨지긴했는데.. 빨간색 부분이 옮기기만 했을뿐
원래 자기 자리는 0으로 바꾸는 작업을 하지 않았다
from sys import stdin
def air_clean(x,y,air_y,after_dust_dict,mode,delta,i):
#움직일 먼지
air_dust = after_dust_dict.get((x,y),0)
#최초 위치는 0으로 만들어 준다
after_dust_dict[(x,y)] = 0
그러면 모든 시뮬레이션이 끝났다... 공기청정기로 옮기고 나서 after_dust_dict를 다시 dust_dict로 초기화시키고 t시간동안 시뮬레이션 수행하고 나서
dust_dict의 dust_dict.values()에 미세먼지들이 저장되어있으니까 sum()으로 구해준다면 그것이 정답
from sys import stdin
def air_clean(x,y,air_y,after_dust_dict,mode,delta,i):
#움직일 먼지
air_dust = after_dust_dict.get((x,y),0)
#최초 위치는 0으로 만들어 준다
after_dust_dict[(x,y)] = 0
while 1:
if mode == 0:
while 1:
dx = x + delta[mode][0]
dy = y + delta[mode][1]
if dx <= c-1:
temp = after_dust_dict.get((dx,dy),0) #움직여야하는 자리의 먼지를 임시 저장해두고
after_dust_dict[(dx,dy)] = air_dust
else: ##범위를 벗어나는 경우..
mode = 1 #위쪽으로 움직이도록
break #움직이지 않고
air_dust = temp #다음에 움직여야할 먼지 양
x = dx
y = dy
elif mode == 1: #위쪽 혹은 아래쪽으로 움직이는 단계
while 1:
dx = x + delta[mode][0]
dy = y + delta[mode][1]
if i == 0:
if dy >= 0:
temp = after_dust_dict.get((dx,dy),0)
after_dust_dict[(dx,dy)] = air_dust
else:
mode = 2
break
else:
if dy <= r-1:
temp = after_dust_dict.get((dx,dy),0)
after_dust_dict[(dx,dy)] = air_dust
else:
mode = 2 #왼쪽으로 움직이는 단계
break
air_dust = temp
x = dx
y = dy
elif mode == 2: #왼쪽으로 움직이는 단계
while 1:
dx = x + delta[mode][0]
dy = y + delta[mode][1]
if dx >= 0:
temp = after_dust_dict.get((dx,dy),0)
after_dust_dict[(dx,dy)] = air_dust
else:
mode = 3
break
air_dust = temp
x = dx
y = dy
elif mode == 3: #위쪽 혹은 아래쪽으로 움직이는 단계
while 1:
dx = x + delta[mode][0]
dy = y + delta[mode][1]
if i == 0:
if dy < air_y:
temp = after_dust_dict.get((dx,dy),0)
after_dust_dict[(dx,dy)] = air_dust
elif dy == air_y:
return after_dust_dict
else:
if dy > air_y:
temp = after_dust_dict.get((dx,dy),0)
after_dust_dict[(dx,dy)] = air_dust
elif dy == air_y:
return after_dust_dict
air_dust = temp
x = dx
y = dy
r,c,t = map(int,stdin.readline().split())
maps = [list(map(int,stdin.readline().split())) for _ in range(r)]
##미세먼지와 공기청정기를 찾는다
dust_dict = {}
air_list = []
for y in range(r):
for x in range(c):
if maps[y][x] >= 1:
dust_dict[(x,y)] = maps[y][x]
elif maps[y][x] == -1:
air_list.append((x,y))
delta = [[0,1],[1,0],[0,-1],[-1,0]]
#시뮬레이션 시작
for _ in range(t):
#미세먼지 확산단계
after_dust_dict = {}
for (x,y),dust in dust_dict.items():
diff_count = 0 #확산되는 수
diffusion = dust//5 #확산되는 양
if diffusion != 0: #확산되는 양이 0이면.. 확산이 안일어남
for ni,nj in delta:
dx = x + ni
dy = y + nj
#확산 범위를 벗어나는지, 공기청정기가 있는지
if dx >= 0 and dx <= c-1 and dy >= 0 and dy <= r-1 and maps[dy][dx] != -1:
diff_count += 1 #확산이 일어났고
after_dust_dict[(dx,dy)] = after_dust_dict.get((dx,dy),0) + diffusion
#하나의 미세먼지가 확산이 끝나면 현재 자리에 남아있는 양을 체크함
remain = dust - (diffusion * diff_count)
after_dust_dict[(x,y)] = after_dust_dict.get((x,y),0) + remain
#공기청정기 단계
air_delta = [[[1,0],[0,-1],[-1,0],[0,1]],[[1,0],[0,1],[-1,0],[0,-1]]]
for i in range(2):
x = air_list[i][0]+1
y = air_list[i][1]
air_y = air_list[i][1]
after_dust_dict = air_clean(x,y,air_y,after_dust_dict,0,air_delta[i],i)
dust_dict = after_dust_dict #다음 단계로 넘어가기 전 초기화
#모든 시뮬레이션이 끝나면
print(sum(dust_dict.values()))
'알고리즘 > 구현,시뮬레이션' 카테고리의 다른 글
| 프로그래밍으로 뱀을 만드는 방법? -뱀- (0) | 2022.11.13 |
|---|---|
| 주사위를 구현하는 방법 - 주사위 굴리기 - (0) | 2022.11.12 |
| deque도 인덱스로 접근해서 원소 수정이 가능하다 -컨베이어 벨트 위의 로봇- (0) | 2022.11.07 |
| 성실하게 시뮬레이션 구현하기.. -로봇 청소기- (0) | 2022.11.03 |
| 0.x초 단위로 시뮬레이션하는 방법 -원자소멸시뮬레이션- (0) | 2022.10.30 |
