시뮬레이션의 기본을 배우는 문제 -미생물 격리-
1. 문제
2382 [모의sw역량테스트] 미생물격리
SW Expert Academy
SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!
swexpertacademy.com
조건에 맞게 이동하는 미생물들이 존재하는 배열에서 특정 시간 이후에 남아있는 미생물의 수를 구하는 문제
2. 풀이1
기본적으로 sw 역량테스트는 문제에서 제시하는 조건대로 성실하게 구현하면 답은 낼 수 있다
일단 문제에서 말하는대로 직관적인 시뮬레이션을 수행해보자
먼저 n*n 배열에 미생물을 그대로 배치하고 싶다
그리고 가장자리는 1로 채워줘야한다. n-2개의 0이 들어간 리스트 좌우 양쪽에 1을 붙인 n-2개의 행을 준비하고,
0행과 n-1행은 1이 n개 채워진 배열을 위 아래로 붙인 n*n 2차원 배열을 준비한다
#문제에서 요구하는대로 직관적으로 시뮬레이션 하자
T = int(input())
for tc in range(1,T+1):
n,m,k = map(int,input().split())
maps = [[1]*n] + [[1]+[0]*(n-2)+[1] for _ in range(n-2)] + [[1]*n]
##최초 미생물 배치
for i in range(k):
y,x,c,d = map(int,input().split())
maps[y][x] = (x,y,c,d,i) ##좌표, 미생물 수, 방향, 미생물의 고유 번호
그리고 최초 맵에 좌표, 미생물 수, 미생물의 방향, 그리고 미생물이 움직였는지 체크하기 위한 고유 번호를 담아둔다
그리고 약품을 만나면 방향이 반대로 바뀐다고 했잖아
문제에서 상,하,좌,우를 1,2,3,4로 제시했고 이것으로 접근하면 바로 방향을 바꿀 수 있게 dictionary를 이용
방향을 나타내는 델타배열을 만들어서..
#약품을 만나면 바꿀 방향
#상 > 하, 하 > 상, 좌> 우, 우 > 좌
change_dir = {1:2, 2:1, 3:4, 4:3} #방향 바꾸기
#시뮬레이션 시작
t = 0
#상하좌우 델타배열
delta = [[0,-1],[0,1],[-1,0],[1,0]]
초기 맵에 미생물들을 모두 배치했으면 t=0부터 1시간 단위로 시뮬레이션을 시작한다.
맵을 모두 순회하여, 미생물이 존재하는지 아닌지를 체크한다.
0이나 1이 아니라면 미생물이 존재하는 것이고 델타배열에 맞게 미생물을 이동시킨다
while 1:
t += 1
final_moving = [] ##미생물이 있는 곳에 이동할때, 이동하지 않은 미생물을 따로 모아둘 배열
join_point = set() ##결합시켜야할 미생물이 존재하는 곳이라면...
move = [0]*k #움직인 미생물 확인
##맵의 모든 점을 순회하여 이동해야할 미생물을 찾는다
for y in range(n):
for x in range(n):
if maps[y][x] != 0 and maps[y][x] != 1: ##미생물 정보가 존재한다면..
if type(maps[y][x]) == list: ##미생물 정보가 리스트로 존재하고 있다면 나중에 결합시켜야할 미생물들이므로 옮길 필요는 없다
continue
a,b,c,d,i = maps[y][x] #미생물 정보를 빼오고
if move[i] == 1: ##이미 이동한 미생물이라면..
continue #이동을 수행하지 않는다
##이동할 좌표 구하기
da = a + delta[d-1][0]
db = b + delta[d-1][1]
2차원 n*n 배열을 순회하면서 미생물이 존재하는지 찾아낼건데, 이전에 미생물을 찾아서 그 미생물을 이동시켰더니
예를 들어 2행 1열을 순회하는 중에 미생물이 존재해서 2행 2열로 미생물을 이동시켰는데, 다음에 2행 2열을 순회할 차례에 미생물을 찾아낼 것이다
하지만 그 미생물은 이전에 이동시켰던 미생물이므로 다시 이동시키면 안된다.
그래서 미생물의 고유번호와 움직였는지 아닌지를 체크하는 move배열을 만들었다
그래서 이동했는지, 아닌지를 체크하고 이동한 미생물이 아니라면 방향 d를 이용해 델타배열에 접근해서 미생물을 이동시킨다
미생물이 이동한 좌표에 존재하는 것이 무엇인지에 따라 행동을 다르게 하면 되는데
if maps[db][da] == 0: #미생물이 이동할 곳이 0이라면
#그냥 이동시키면 됨
maps[db][da] = (da,db,c,d,i)
move[i] = 1
elif maps[db][da] == 1: ##미생물이 이동할 곳이 1이라면
c = c//2 #미생물 절반 소멸
if c == 0: #미생물 수가 0이면
##이동하기 전의 위치를 좌표에 따라 0아니면 1로 채워넣고
if x == 0 or x == n-1 or y == 0 or y == n-1:
maps[y][x] = 1
else:
maps[y][x] = 0
continue ## 해당 미생물 군집을 소멸시키자
else: ##절반이 소멸되어도 미생물 수가 남아있다면
d = change_dir[d] #미생물 방향 바꾸고
maps[db][da] = (da,db,c,d,i) ##미생물 배치
move[i] = 1
이동을 했더니 0이라면 아무 일 없이 그냥 이동시키면 된다
그런데 1이라면, 약품을 만났으므로 미생물 수를 절반 소멸시킨다
그런데 절반을 소멸시켰더니 남아있는 미생물 수가 0이라면, 그 미생물을 제거해야한다
아직 이동을 해서 map에 배치한 것은 아니기 때문에 이동하기 전인 x,y에 미생물 정보가 존재한다.
이동하기 전의 좌표가 무엇인지에 따라 maps[y][x]를 0 아니면 1로 채워넣으면 미생물이 맵에서 제거된다
약품의 위치는 가장자리이므로 행 y가 0 아니면 n-1이거나, 열 x가 0 아니면 n-1일때 가장자리가 된다.
그런데 절반을 소멸시켜도 여전히 미생물 수가 존재한다면...
방향을 반대로 바꿔주고 해당 위치에 미생물을 배치시키면 된다
다음으로 가장 어려운 부분이 이동을 했는데 미생물이 존재하는 경우이다.
else: ##이동한 위치에 미생물이 존재한다면..
##그런데 미생물이 결합할 수 있는 위치는 약품이 있는 위치에서는 절대로 불가능하다
if type(maps[db][da]) == list: ##결합시켜야할 미생물들이 모여있다면
maps[db][da].append((c,d,i)) #이동할 미생물도 그대로 넣는다
move[i] = 1
elif type(maps[db][da]) == tuple: #미생물이 하나만 존재하고 있다면
if move[maps[db][da][4]] == 1: #이미 움직였던 미생물이라면..
temp = [(maps[db][da][2],maps[db][da][3],maps[db][da][4])]
temp.append((c,d,i)) ##나중에 결합을 시키기 위해 미생물들을 리스트로 모아둔다
move[i] = 1
maps[db][da] = temp
join_point.add((da,db)) #결합시켜야할 미생물이 존재하는 위치를 따로 모아둔다
결합을 한다면, 약품이 있는 위치에서 결합하는 것은 절대로 불가능하다
왜냐하면 상하좌우로 움직이는데 가장자리에서 서로 만날수가 있는지 잘 생각해보면, 절대로 만날수 없다는 것을 알 수 있다
먼저 미생물을 결합시킬거면, 미생물들을 리스트에 모아놓을것이다.
그러니까 맵에서 이동했는데, 리스트가 존재한다면, 미생물을 그대로 리스트에 넣어두고 나중에 결합단계에서 미생물을 결합시키자
리스트 말고 튜플이 존재하는 경우에는 해당 미생물이 움직인 미생물이냐, 아니면 아직 움직이지 않은 미생물이냐에 따라 다르다
이게 문제를 보면 아직 이동하지 않은 미생물을 만나면 합쳐지는게 아니라 갈길 간다는게 문제다
그러니까 이동을 했는데 이미 이동을 끝낸 미생물을 만난다면, 리스트에 모아놓을 것이다
애초에 그 자리에서 결합을 할 것이므로 리스트를 새로 만들어서 현재 존재하는 미생물 정보를 담은 temp에다가
새로 들어온 미생물의 정보를 append 시킨다
결합단계에서는 좌표는 필요없고 미생물 수, 방향, 고유번호만 필요하다
나중에 따로 결합시키기 위해 어느 위치에 결합이 일어나는지 모아놓은 좌표 set이 joint_point이다
그런데 아직 움직이지 않은 미생물을 만난다면? 여기가 제일 어려웠다
else: #아직 움직이지 않은 미생물이 존재한다면
final_moving.append(maps[db][da]) #움직이지 않은 친구는 나중에 따로 옮기기 위해 모아두고
##여기서도 약품이 있는 위치로 온건 아닌지 검사해야함
##이곳으로 이동한 미생물에 대하여...
if da == 0 or da == n-1 or db == 0 or db == n-1: #약품이 존재하는 위치라면
c = c//2 ##미생물을 절반 소멸시키고
if c == 0:
##이동하기 전 자리를 다시 0아니면 1로 채워놔야지
if x == 0 or x == n-1 or y == 0 or y == n-1:
maps[y][x] = 1
else:
maps[y][x] = 0
continue
else: ##절반을 소멸해도 미생물이 남아있다면
d = change_dir[d] ##방향을 바꾸고 배치한다
##미생물을 배치
##약품이 존재하는 곳에 이동했다면.. 위에 if문에 의해 미생물 수를 절반으로 줄였고 방향도 바뀜
##약품이 존재하지 않은 곳으로 이동했다면.. 그냥 그대로 배치가 됨
maps[db][da] = (da,db,c,d,i)
move[i] = 1
이 역시 final_moving이라는 리스트를 새로 하나 만들었다.
아직 움직이지 않은 미생물을 만나게 된다면, 그러한 미생물은 final_moving이라는 리스트에 전부 담아둔다음에
모든 맵을 순회하고 나서, 나중에 final_moving을 순회하여 움직이지 않은 미생물을 움직이도록 만든다
아무튼 방해되는 미생물은 이제 치워버리고 이동한 미생물의 위치가 약품이 존재하는 위치인지,
약품이 존재하는 위치가 아닌지 2가지 경우에서 따져야한다
약품이 존재하면, 미생물 절반을 소멸시키고 그럴때 미생물 수가 0이 된다면 위치에 따라 0아니면 1로 map을 채워넣으면 된다
아니라면 미생물 옮긴걸 배치시키면 된다
여기까지 오면 맵에 존재하는 미생물을 일차적으로 옮긴건데 옮기기 전에 배치된 미생물을 지워줘야겠지
##이제 미생물을 옮기고 옮기기 전 자리를 0,1로 채워줘야함
if x == 0 or x == n-1 or y == 0 or y == n-1:
maps[y][x] = 1
else:
maps[y][x] = 0
소멸시키는 것 이외에는 원래 자리에 0 아니면 1을 채워넣지는 않았다
아무튼 x가 0아니면 n-1이거나 y가 0아니면 n-1이면 약품이 존재하는 곳이니 1을 넣고 아니라면 0을 넣으면 된다
이제 일차적으로 미생물을 옮겼다
하지만 결합시키는 과정과 아직 미생물을 옮기지 않은 경우가 있었다
##다 옮기고 나서 옮기지 않은 미생물을 옮기는 단계
#이 단계로 왔다면, 이미 map에 존재하는 미생물들은 전부 옮기는 것을 완료함
##옮겨야할 미생물만 고려하면 된다
for a,b,c,d,i in final_moving:
#미생물이 이동할 좌표
da = a + delta[d-1][0]
db = b + delta[d-1][1]
if maps[db][da] == 0: ##이동한 곳이 0이라면 그냥 옮기면 된다
maps[db][da] = (da,db,c,d,i)
elif maps[db][da] == 1: ##이동한 곳이 1이라면.. 약품을 만났으므로
c = c//2 ##절반을 소멸시키고
if c == 0: ##미생물 수가 0이라면 소멸시킨다
continue
else: ##미생물 수가 존재하고 있다면..
d = change_dir[d] ##방향을 바꾸고 배치
maps[db][da] = (da,db,c,d,i)
else: ##미생물이 존재하는 곳에 이동한다면..
if type(maps[db][da]) == list: #결합시켜야할 미생물들이 존재하고 있다면
maps[db][da].append((c,d,i)) ##결합을 위해 리스트에 넣어두고
else: ##미생물이 하나만 존재한다면..
##그 미생물은 이미 이동을 마친 미생물이므로
##그냥 두 미생물을 리스트로 만들어서 저장
temp = [(maps[db][da][2], maps[db][da][3], maps[db][da][4])]
temp.append((c,d,i))
maps[db][da] = temp
join_point.add((da,db))
##밖에서 배치하므로, 옮기기 전 좌표에 대해 0,1로 다시 채울필요는 없음
먼저 미생물을 옮기는 와중에 서로 만났는데, 아직 이동하지 않은 미생물을 만난 경우 그러한 미생물은 final_moving에 담아뒀는데
이 리스트에 있는 미생물을 먼저 옮겨줘야한다.
이 미생물이 이동하는 단계에서는 현재 map에는 모두 이동한 미생물들만 존재하게 된다.
그래서 이동했더니 map값이 0이면 그대로 이동시키면 되고 1을 만나면 절반을 줄여서 소멸시키거나 방향을 바꾸고 배치하거나
그 외에 미생물이 존재하는 곳에 이동한다면, 만약 리스트라면 나중에 결합을 위해 리스트에 append시키거나
미생물 하나만 존재하는 곳이라면, 그 미생물은 이미 이동했던 미생물이니 서로 결합시켜줘야해서 리스트를 만들어서 담아둔다
여기 미생물들은 map 밖에서 배치했으므로 이동하고 나서 map의 원래 자리를 0 아니면 1로 채워넣는 과정은 필요없다
##미생물을 결합하는 단계
for a,b in join_point:
#미생물이 가장 많은 순서대로 정렬
#(a,b) 위치에서 가장 미생물 수가 많은 미생물을 찾는다
sorted_temp = sorted(maps[b][a], key = lambda item: -item[0])
d = sorted_temp[0][1] #가장 많은 수의 미생물의 방향
c = 0 #미생물 결합하면 가질 미생물 수
max_ind = 0 ##고유번호는 그냥 미생물들 고유번호의 최댓값으로 변경
for x,y,i in sorted_temp:
c += x ##존재하는 미생물 수를 모두 더해준다
if max_ind < i:
max_ind = i
maps[b][a] = (a,b,c,d,max_ind) ##결합되는 지점에 미생물을 재배치
다음으로 결합시키는 단계에서는 결합 자리에는 joint_point라는 set에 결합 지점을 모두 담아뒀다
그 set을 순회해서 얻은 좌표를 넣으면 결합해야할 리스트를 얻는데
문제 조건에서 미생물 수가 가장 많은 미생물의 방향으로 만들어야하니 리스트를 정렬시켜서 가장 많은 수를 가진 미생물의 방향을 구하자.
미생물들이 가지는 미생물 수의 합으로 미생물 군집을 만들게 된다
고유번호는 어떤 것으로 해도 상관없겠지만, 편의상 고유번호가 가장 큰 것으로 바꿔줬다
최종 결합을 마치면 map에 좌표, 미생물 수, 방향, 고유번호를 배치시켰다
if t == m: ##m시간까지 끝나면 break
break
ans = 0
for y in range(n):
for x in range(n):
if maps[y][x] != 0 and maps[y][x] != 1:
ans += maps[y][x][2] ##m시간 후 맵을 순회하여 미생물이 존재하는 곳의 미생물 수를 모두 더해준다
print('#'+str(tc),ans)
이러면 1시간 단위의 시뮬레이션이 끝난거다.
m시간까지 끝나면 while문을 탈출하고 만들어진 맵을 전부 순회한다
순회해서 0도 아니고 1도 아닌곳에는 미생물이 존재하는 곳이고, 그 미생물들의 수를 누적시켜서 구하면...
m시간 후 남아있는 미생물 수가 될 것
#문제에서 요구하는대로 직관적으로 시뮬레이션 하자
T = int(input())
for tc in range(1,T+1):
n,m,k = map(int,input().split())
maps = [[1]*n] + [[1]+[0]*(n-2)+[1] for _ in range(n-2)] + [[1]*n]
##최초 미생물 배치
for i in range(k):
y,x,c,d = map(int,input().split())
maps[y][x] = (x,y,c,d,i) ##좌표, 미생물 수, 방향, 미생물의 고유 번호
#약품을 만나면 바꿀 방향
#상 > 하, 하 > 상, 좌> 우, 우 > 좌
change_dir = {1:2, 2:1, 3:4, 4:3} #방향 바꾸기
#시뮬레이션 시작
t = 0
#상하좌우 델타배열
delta = [[0,-1],[0,1],[-1,0],[1,0]]
while 1:
t += 1
final_moving = [] ##미생물이 있는 곳에 이동할때, 이동하지 않은 미생물을 따로 모아둘 배열
join_point = set() ##결합시켜야할 미생물이 존재하는 곳이라면...
move = [0]*k #움직인 미생물 확인
##맵의 모든 점을 순회하여 이동해야할 미생물을 찾는다
for y in range(n):
for x in range(n):
if maps[y][x] != 0 and maps[y][x] != 1: ##미생물 정보가 존재한다면..
if type(maps[y][x]) == list: ##미생물 정보가 리스트로 존재하고 있다면 나중에 결합시켜야할 미생물들이므로 옮길 필요는 없다
continue
a,b,c,d,i = maps[y][x] #미생물 정보를 빼오고
if move[i] == 1: ##이미 이동한 미생물이라면..
continue #이동을 수행하지 않는다
##이동할 좌표 구하기
da = a + delta[d-1][0]
db = b + delta[d-1][1]
if maps[db][da] == 0: #미생물이 이동할 곳이 0이라면
#그냥 이동시키면 됨
maps[db][da] = (da,db,c,d,i)
move[i] = 1
elif maps[db][da] == 1: ##미생물이 이동할 곳이 1이라면
c = c//2 #미생물 절반 소멸
if c == 0: #미생물 수가 0이면
##이동하기 전의 위치를 좌표에 따라 0아니면 1로 채워넣고
if x == 0 or x == n-1 or y == 0 or y == n-1:
maps[y][x] = 1
else:
maps[y][x] = 0
continue ## 해당 미생물 군집을 소멸시키자
else: ##절반이 소멸되어도 미생물 수가 남아있다면
d = change_dir[d] #미생물 방향 바꾸고
maps[db][da] = (da,db,c,d,i) ##미생물 배치
move[i] = 1
else: ##이동한 위치에 미생물이 존재한다면..
##그런데 미생물이 결합할 수 있는 위치는 약품이 있는 위치에서는 절대로 불가능하다
if type(maps[db][da]) == list: ##결합시켜야할 미생물들이 모여있다면
maps[db][da].append((c,d,i)) #이동할 미생물도 그대로 넣는다
move[i] = 1
elif type(maps[db][da]) == tuple: #미생물이 하나만 존재하고 있다면
if move[maps[db][da][4]] == 1: #이미 움직였던 미생물이라면..
temp = [(maps[db][da][2],maps[db][da][3],maps[db][da][4])]
temp.append((c,d,i)) ##나중에 결합을 시키기 위해 미생물들을 리스트로 모아둔다
move[i] = 1
maps[db][da] = temp
join_point.add((da,db)) #결합시켜야할 미생물이 존재하는 위치를 따로 모아둔다
else: #아직 움직이지 않은 미생물이 존재한다면
final_moving.append(maps[db][da]) #움직이지 않은 친구는 나중에 따로 옮기기 위해 모아두고
##여기서도 약품이 있는 위치로 온건 아닌지 검사해야함
##이곳으로 이동한 미생물에 대하여...
if da == 0 or da == n-1 or db == 0 or db == n-1: #약품이 존재하는 위치라면
c = c//2 ##미생물을 절반 소멸시키고
if c == 0:
##이동하기 전 자리를 다시 0아니면 1로 채워놔야지
if x == 0 or x == n-1 or y == 0 or y == n-1:
maps[y][x] = 1
else:
maps[y][x] = 0
continue
else: ##절반을 소멸해도 미생물이 남아있다면
d = change_dir[d] ##방향을 바꾸고 배치한다
##미생물을 배치
##약품이 존재하는 곳에 이동했다면.. 위에 if문에 의해 미생물 수를 절반으로 줄였고 방향도 바뀜
##약품이 존재하지 않은 곳으로 이동했다면.. 그냥 그대로 배치가 됨
maps[db][da] = (da,db,c,d,i)
move[i] = 1
##이제 미생물을 옮기고 옮기기 전 자리를 0,1로 채워줘야함
if x == 0 or x == n-1 or y == 0 or y == n-1:
maps[y][x] = 1
else:
maps[y][x] = 0
##다 옮기고 나서 옮기지 않은 미생물을 옮기는 단계
#이 단계로 왔다면, 이미 map에 존재하는 미생물들은 전부 옮기는 것을 완료함
##옮겨야할 미생물만 고려하면 된다
for a,b,c,d,i in final_moving:
#미생물이 이동할 좌표
da = a + delta[d-1][0]
db = b + delta[d-1][1]
if maps[db][da] == 0: ##이동한 곳이 0이라면 그냥 옮기면 된다
maps[db][da] = (da,db,c,d,i)
elif maps[db][da] == 1: ##이동한 곳이 1이라면.. 약품을 만났으므로
c = c//2 ##절반을 소멸시키고
if c == 0: ##미생물 수가 0이라면 소멸시킨다
continue
else: ##미생물 수가 존재하고 있다면..
d = change_dir[d] ##방향을 바꾸고 배치
maps[db][da] = (da,db,c,d,i)
else: ##미생물이 존재하는 곳에 이동한다면..
if type(maps[db][da]) == list: #결합시켜야할 미생물들이 존재하고 있다면
maps[db][da].append((c,d,i)) ##결합을 위해 리스트에 넣어두고
else: ##미생물이 하나만 존재한다면..
##그 미생물은 이미 이동을 마친 미생물이므로
##그냥 두 미생물을 리스트로 만들어서 저장
temp = [(maps[db][da][2], maps[db][da][3], maps[db][da][4])]
temp.append((c,d,i))
maps[db][da] = temp
join_point.add((da,db))
##밖에서 배치하므로, 옮기기 전 좌표에 대해 0,1로 다시 채울필요는 없음
##미생물을 결합하는 단계
for a,b in join_point:
#미생물이 가장 많은 순서대로 정렬
#(a,b) 위치에서 가장 미생물 수가 많은 미생물을 찾는다
sorted_temp = sorted(maps[b][a], key = lambda item: -item[0])
d = sorted_temp[0][1] #가장 많은 수의 미생물의 방향
c = 0 #미생물 결합하면 가질 미생물 수
max_ind = 0 ##고유번호는 그냥 미생물들 고유번호의 최댓값으로 변경
for x,y,i in sorted_temp:
c += x ##존재하는 미생물 수를 모두 더해준다
if max_ind < i:
max_ind = i
maps[b][a] = (a,b,c,d,max_ind) ##결합되는 지점에 미생물을 재배치
if t == m: ##m시간까지 끝나면 break
break
ans = 0
for y in range(n):
for x in range(n):
if maps[y][x] != 0 and maps[y][x] != 1:
ans += maps[y][x][2] ##m시간 후 맵을 순회하여 미생물이 존재하는 곳의 미생물 수를 모두 더해준다
print('#'+str(tc),ans)
3. 풀이2
아주 오랜 시간 왜 틀렸는지 눈 빠지게 고쳐가지고 맞추긴했는데
요구하는대로 정확하게 시뮬레이션한거 분명히 좋았는데
남들 0.5초에 50개 맞추는 문제를 3초나 걸렸으니 당연히 아쉽다
최적화 시키는 방법이 있을까
먼저 map에 배치할때, x,y좌표를 저장할 필요가 있을까?
map을 순회하면서 미생물을 만나면, 좌표는 당연히 따라오는건데 굳이 좌표까지 저장할 필요는 없다
그리고 미생물이 한 지점에 모이면 그러한 미생물을 리스트에 담아두고 나중에 한번에 결합시켰는데..
모일때마다 미생물을 결합시키는 놀라운 방법이 존재한다
그거는 미생물을 배치할때, 이 위치에 있는 미생물 수의 최댓값도 같이 저장해놓는것이다
#현재 위치에 모인 미생물들중 가장 큰 미생물 수를 가진 미생물 정보도 같이 저장해놓기
#미생물 결합단계를 제거하고 모일때마다 결합시키자
#x,y좌표도 저장할 필요가 있나?? 2차원 배열 map에 배치해놓을건데
T = int(input())
for tc in range(1,T+1):
n,m,k = map(int,input().split())
maps = [[1]*n] + [[1]+[0]*(n-2)+[1] for _ in range(n-2)] + [[1]*n]
##최초 미생물 배치
for i in range(k):
y,x,c,d = map(int,input().split())
##(x,y)에 모인 미생물 군집의 미생물 수의 총합, 움직이는 방향,
##,고유번호, 군집에 모인 미생물 종류별로 가지는 미생물 수 중 가장 큰 미생물 수
maps[y][x] = (c,d,i,c)
최초 배치할때는 현재 (x,y)에 존재하는 미생물 수는 c인데, 1마리만 존재하는거니까
당연히 이 위치에 모인 미생물 군집에서 미생물들의 수중 최댓값은 c가 된다
그래서 map에 배치할때 (군집의 미생물 총 수, 방향, 고유 번호, 군집에 모인 미생물 수중 최댓값)
으로 배치해둔다면??
현재 위치 (x,y)에 미생물이 모일때마다 "군집에 모인 미생물 수중 최댓값"을 비교해가면서
새로 들어온 미생물의 수가 현재 위치의 "군집에 모인 미생물 수중 최댓값"보다 크다면, 방향을 바꿔주고 이 최댓값도 갱신시키면 된다
그러면 미생물이 모일때마다 결합이 가능해지고 나중에 결합하는 단계도 제거할 수 있다
for _ in range(m): ##m시간만 돌면 되니까
final_moving = []
move = [0]*k #움직인 미생물 확인
##모든 점을 순회하여 이동해야할 미생물을 찾는다
for y in range(n):
for x in range(n):
if maps[y][x] != 0 and maps[y][x] != 1: ##미생물 정보가 존재한다면..
c,d,i,max_c = maps[y][x] #미생물 정보를 빼오고
if move[i] == 1: ##이동한 미생물이라면..
continue #수행하지 않는다
##이동할 좌표 구하기
dx = x + delta[d-1][0]
dy = y + delta[d-1][1]
if maps[dy][dx] == 0: #이동한 곳이 0이라면
#그냥 이동시키면 됨
maps[dy][dx] = (c,d,i,c)
move[i] = 1
elif maps[dy][dx] == 1: ##이동한 곳이 1이라면
c = c//2 #미생물 절반 소멸
if c != 0: #절반 소멸해도 미생물이 존재한다면
d = change_dir[d] #방향 바꾸고
maps[dy][dx] = (c,d,i,c) #현재 위치에 존재하는 미생물 수의 최댓값은 1마리만 존재하므로 c이다
move[i] = 1
조금 더 깔끔하게 고쳤는데 m시간만 돌면 되니까 for _ in range(m)으로 m번만 돌고
이제 이동했는데 리스트인 경우는 존재하지 않으니 0도 아니고 1도 아니면 튜플이라서 미생물 정보를 바로 빼올 수 있고
절반 소멸시킬때 0이 아닌경우만 작성했다.. 0이면 아무것도 안하면 소멸되는거라서
그리고 여기서 사소하지만 아주 중요한 부분이 있는데
미생물 정보를 빼올때
c,d,i,max_c = maps[y][x]라고 써야한다
c,d,i,c = maps[y][x] 이렇게 쓰면 왜 안될까??
c와 max_c가 다를 수 있기 때문이다.
왜냐하면 m번 반복을 하다보면, 여러 미생물이 결합한 미생물이 움직일 수도 있는데, 그런 경우에는 c와 max_c가 다르기 때문이다
이런 사소한 디테일 놓쳐서 시간좀 걸렸지
else: ##이동했더니 미생물이 존재한다면..
##미생물이 결합할 수 있는 위치는 약품이 있는 위치에서는 불가능하다
if move[maps[dy][dx][2]] == 1: #이미 움직였던 미생물이라면.. 하나로 결합을 시키자
old_c, old_d, old_i, old_max = maps[dy][dx] # vs. 새로 들어온 c,d,i,max_c
if old_max < c: #존재했던 미생물 군집들 중 미생물 수의 최댓값보다 새로 들어온 미생물의 수가 더 크다면
#최댓값을 갱신하고
old_max = c
#방향도 새로 갱신한다
old_d = d
old_c += c #미생물 수를 늘리고
maps[dy][dx] = (old_c,old_d,old_i,old_max)
else: #움직이지 않은 미생물이 존재한다면
final_moving.append((dx,dy,maps[dy][dx])) #움직이지 않은 친구는 따로 옮겨놓고
##여기서도 약품이 있는 위치로 온건 아닌지 검사해야함
if dy == 0 or dy == n-1 or dx == 0 or dx == n-1:
c = c//2
if c != 0:
d = change_dir[d]
maps[dy][dx] = (c,d,i,c)
move[i] = 1
else:
maps[dy][dx] = (c,d,i,c)
move[i] = 1
##미생물을 옮기고 옮기기 전 자리를 0,1로 채워줘야함
if x == 0 or x == n-1 or y == 0 or y == n-1:
maps[y][x] = 1
else:
maps[y][x] = 0
이제 미생물을 만났을때 단계가 조금 달라지겠지..
이동을 했는데 미생물을 만난 경우, 이미 이동했던 미생물이냐, 아니면 이동하지 않은 미생물이냐?
이동하지 않은 미생물이라면.. 그러한 미생물은 final_moving이라는 리스트에 담아둬서 나중에 처리한다
이미 이동했던 미생물이라면 즉시 결합을 시킨다
현재 위치에 존재하는 미생물의 총 수, 방향, 번호, 모인 미생물 수의 최댓값 old_c, old_d, old_i, old_max
새로 들어온 미생물의 수, 방향, 번호, 최댓값 c,d,i,max_c를 서로 비교한다
문제 조건에 따라, 현재 위치에 존재하는 미생물 수의 최댓값인 old_max보다 새로 들어온 미생물의 수 c가 더 크다면
새로 들어온 미생물이 가지는 방향으로 바뀐다는점
그리고 현재 위치로 모인 미생물 군집의 미생물 수의 최댓값도 c로 갱신이 되겠지
그래서 맵에 배치할때, 현재 위치 (x,y)에 모인 미생물 군집들중 최댓값을 가지는 미생물 수까지 저장해놓으면
모이자마자 결합시킬 수 있다는 점
이러면 1시간 시뮬레이션이 끝났다.
다음에는 아직 이동하지 않았던 미생물이 모인 final_moving의 미생물을 옮기면 된다.
#현재 위치에 모인 미생물들중 가장 큰 미생물 수를 가진 미생물 정보도 같이 저장해놓기
#미생물 결합단계를 제거하고 모일때마다 결합시키자
#x,y좌표도 저장할 필요가 있나?? 2차원 배열 map에 배치해놓을건데
T = int(input())
for tc in range(1,T+1):
n,m,k = map(int,input().split())
maps = [[1]*n] + [[1]+[0]*(n-2)+[1] for _ in range(n-2)] + [[1]*n]
##최초 미생물 배치
for i in range(k):
y,x,c,d = map(int,input().split())
maps[y][x] = (c,d,i,c) ##(x,y)에 모인 미생물 군집의 미생물 수의 총합, 움직이는 방향, 고유번호, 군집에 모인 미생물 종류별로 가지는 미생물 수 중 가장 큰 미생물 수
#약품에 위치하면 바꿔야할 방향
#상 > 하, 하> 상, 좌> 우, 우>좌
change_dir = {1:2, 2:1, 3:4, 4:3}
#시뮬레이션 시작
#상하좌우 델타배열
delta = [[0,-1],[0,1],[-1,0],[1,0]]
for _ in range(m): ##m시간만 돌면 되니까
final_moving = []
move = [0]*k #움직인 미생물 확인
##모든 점을 순회하여 이동해야할 미생물을 찾는다
for y in range(n):
for x in range(n):
if maps[y][x] != 0 and maps[y][x] != 1: ##미생물 정보가 존재한다면..
c,d,i,max_c = maps[y][x] #미생물 정보를 빼오고
if move[i] == 1: ##이동한 미생물이라면..
continue #수행하지 않는다
##이동할 좌표 구하기
dx = x + delta[d-1][0]
dy = y + delta[d-1][1]
if maps[dy][dx] == 0: #이동한 곳이 0이라면
#그냥 이동시키면 됨
maps[dy][dx] = (c,d,i,c)
move[i] = 1
elif maps[dy][dx] == 1: ##이동한 곳이 1이라면
c = c//2 #미생물 절반 소멸
if c != 0: #절반 소멸해도 미생물이 존재한다면
d = change_dir[d] #방향 바꾸고
maps[dy][dx] = (c,d,i,c) #현재 위치에 존재하는 미생물 수의 최댓값은 1마리만 존재하므로 c이다
move[i] = 1
else: ##이동했더니 미생물이 존재한다면..
##미생물이 결합할 수 있는 위치는 약품이 있는 위치에서는 불가능하다
if move[maps[dy][dx][2]] == 1: #이미 움직였던 미생물이라면.. 하나로 결합을 시키자
old_c, old_d, old_i, old_max = maps[dy][dx] # vs. 새로 들어온 c,d,i,max_c
if old_max < c: #존재했던 미생물 군집들 중 미생물 수의 최댓값보다 새로 들어온 미생물의 수가 더 크다면
#최댓값을 갱신하고
old_max = c
#방향도 새로 갱신한다
old_d = d
old_c += c #미생물 수를 늘리고
maps[dy][dx] = (old_c,old_d,old_i,old_max)
else: #움직이지 않은 미생물이 존재한다면
final_moving.append((dx,dy,maps[dy][dx])) #움직이지 않은 친구는 따로 옮겨놓고
##여기서도 약품이 있는 위치로 온건 아닌지 검사해야함
if dy == 0 or dy == n-1 or dx == 0 or dx == n-1:
c = c//2
if c != 0:
d = change_dir[d]
maps[dy][dx] = (c,d,i,c)
move[i] = 1
else:
maps[dy][dx] = (c,d,i,c)
move[i] = 1
##미생물을 옮기고 옮기기 전 자리를 0,1로 채워줘야함
if x == 0 or x == n-1 or y == 0 or y == n-1:
maps[y][x] = 1
else:
maps[y][x] = 0
##다 옮기고 나서 옮기지 않은 미생물을 옮기는 단계
#이미 map에 존재하는 미생물은 전부 옮기는 것을 완료함
for x,y,(c,d,i,max_c) in final_moving:
#이동할 좌표
dx = x + delta[d-1][0]
dy = y + delta[d-1][1]
if maps[dy][dx] == 0:
maps[dy][dx] = (c,d,i,c)
elif maps[dy][dx] == 1:
c = c//2
if c != 0:
d = change_dir[d]
maps[dy][dx] = (c,d,i,c)
else:
old_c, old_d, old_i, old_max = maps[dy][dx] # vs. 새로 들어온 c,d,i,max_c
if old_max < c: #존재했던 미생물 군집들 중 미생물 수의 최댓값보다 새로 들어온 미생물의 수가 더 크다면
#최댓값을 갱신하고
old_max = c
#방향도 새로 갱신한다
old_d = d
old_c += c #미생물 수를 늘리고
maps[dy][dx] = (old_c,old_d,old_i,old_max) #고유 번호도 새로 들어온 미생물의 번호로 바꿔주자
ans = 0
for y in range(n):
for x in range(n):
if maps[y][x] != 0 and maps[y][x] != 1:
ans += maps[y][x][0]
print('#'+str(tc),ans)
m시간 시뮬레이션이 끝나고 맵을 다시 순회해서 0도 아니고 1도 아닌 곳에 미생물이 존재하며, 그 미생물 수를 누적시키면 정답이 된다
4. 풀이3
한번에 모아서 나중에 결합시키는 단계를 제거했더니 한 단계 더 욕심이 나는게
시뮬레이션 단계에서 이동하기 전 map과 이동한 후 map을 따로 관리한다면, final_moving을 제거할 수 있지 않을까?
애초에 map하나에 이동을 하니까
이동하기 전인 미생물을 만나면.. 이게 겹쳐가지고 따로 빼서 나중에 옮기잖아
이동하기 전의 미생물들을 이동시키면 이동한 후인 map에 배치시킨다면...
미생물이 이동할때 이동하지 않은 미생물을 만날리는 없다
그리고 이렇게 하면 move배열도 필요가 없다.. 이동한 미생물은 after_maps라는 다른 공간에 존재해버리니까
그래서 고유번호도 저장할 필요도 없어
#이번엔 이동하기 전 map과 이동한 후 map을 따로 관리해서
#이동했더니 만난 미생물이 이동하지 않은 미생물일때, 따로 옮기는 작업도 제거해
T = int(input())
for tc in range(1,T+1):
n,m,k = map(int,input().split())
before_maps = [[1]*n] + [[1]+[0]*(n-2)+[1] for _ in range(n-2)] + [[1]*n]
##최초 미생물 배치
for i in range(k):
y,x,c,d = map(int,input().split())
#그러면 고유 번호도 필요가 없어
#이동하지 않은 맵에는 이동하지 않은 미생물만 존재하니까
before_maps[y][x] = (c,d,c) ##(x,y)에 모인 미생물 군집의 미생물 수의 총합, 움직이는 방향, 군집에 모인 미생물 종류별로 가지는 미생물 수 중 가장 큰 미생물 수
#약품에 위치하면 바꿔야할 방향
#상 > 하, 하> 상, 좌> 우, 우>좌
change_dir = {1:2, 2:1, 3:4, 4:3}
#시뮬레이션 시작
#상하좌우 델타배열
delta = [[0,-1],[0,1],[-1,0],[1,0]]
for _ in range(m): ##m시간만 돌면 되니까
#이동 후에 배치되는 맵
after_maps = [[1]*n] + [[1]+[0]*(n-2)+[1] for _ in range(n-2)] + [[1]*n]
##모든 점을 순회하여 이동해야할 미생물을 찾는다
for y in range(n):
for x in range(n):
if before_maps[y][x] != 0 and before_maps[y][x] != 1: ##미생물 정보가 존재한다면..
c,d,max_c = before_maps[y][x] #미생물 정보를 빼오고
##이동할 좌표 구하기
dx = x + delta[d-1][0]
dy = y + delta[d-1][1]
if after_maps[dy][dx] == 0: #이동한 곳이 0이라면
#그냥 이동시키면 됨
after_maps[dy][dx] = (c,d,c)
elif after_maps[dy][dx] == 1: ##이동한 곳이 1이라면
c = c//2 #미생물 절반 소멸
if c != 0: #절반 소멸해도 미생물이 존재한다면
d = change_dir[d] #방향 바꾸고
after_maps[dy][dx] = (c,d,c) #현재 위치에 존재하는 미생물 수의 최댓값은 1마리만 존재하므로 c이다
else: ##이동했더니 미생물이 존재한다면..
##미생물이 결합할 수 있는 위치는 약품이 있는 위치에서는 불가능하다
old_c, old_d, old_max = after_maps[dy][dx] # vs. 새로 들어온 c,d,max_c
if old_max < c: #존재했던 미생물 군집들 중 미생물 수의 최댓값보다 새로 들어온 미생물의 수가 더 크다면
#최댓값을 갱신하고
old_max = c
#방향도 새로 갱신한다
old_d = d
old_c += c #미생물 수를 늘리고
after_maps[dy][dx] = (old_c,old_d,old_max)
before_maps = after_maps ##다음 시간으로 넘어가기 전에 map 초기화
ans = 0
for y in range(n):
for x in range(n):
if after_maps[y][x] != 0 and after_maps[y][x] != 1:
ans += after_maps[y][x][0]
print('#'+str(tc),ans)
로직은 이제 지금까지 해왔던거랑 동일한데 시뮬레이션마다 after_maps를 초기화해서 만들어줘야하고
before_maps에서 이동하지 않은 미생물을 찾아서 이동을 시키면 after_maps에 배치하면 된다
아무튼 이러면 이동하지 않은 미생물을 만날리는 없으니까 final_moving단계를 없앨 수 있다
5. 풀이4
근데 조금 더 생각을 해보면 이게.. map에 배치를 해야하나??
2차원 배열에 배치하고 하나씩 옮기는것 자체가 문제야
2차원 배열을 순회해가지고 미생물을 찾아내는 것도 상당히 시간낭비임
좌표를 대응시켜서 미생물의 정보를 바로 알 수 있게 dictionary로 따로 관리하자
좌표 (x,y)를 key로 하고 (미생물의 수, 미생물 방향, 미생물 군집에 모인 미생물 수 최댓값)을 value로 한 dictionary를 만들자
그리고 이동하기 전인 before_maps와 이동한 후인 after_maps를 따로 관리하자.
그리고 약품의 위치는? 사실 미생물의 좌표만 이용하면 바로 알 수 있잖아
x가 0아니면 n-1이거나 y가 0아니면 n-1이면.. 약품이었으니까
이렇게 dictionary로 관리하면.. n*n을 순회하는 것도 아니고 dictionary를 순회하면 미생물들만 찾아낼 수 있으니까 상당한 시간이 절약될 것이다
#이제는 맵에 배치하지도 말아
#약품의 위치는 미생물의 좌표만 알면 바로 알 수 있어
#미생물의 정보를 좌표만 넣으면 바로 알 수 있게 dictionary에 따로 관리
#그러면 n*n 이중 for문 순회하는것도 제거가 될것
T = int(input())
for tc in range(1,T+1):
n,m,k = map(int,input().split())
before_maps = {}
##최초 미생물 배치
for _ in range(k):
y,x,c,d = map(int,input().split())
#좌표를 key로 해서 미생물의 정보를 바로 가져오도록
before_maps[(x,y)] = (c,d,c) ##(x,y)에 모인 미생물 군집의 미생물 수의 총합, 움직이는 방향, 군집에 모인 미생물 종류별로 가지는 미생물 수 중 가장 큰 미생물 수
#약품에 위치하면 바꿔야할 방향
#상 > 하, 하> 상, 좌> 우, 우>좌
change_dir = {1:2, 2:1, 3:4, 4:3}
#시뮬레이션 시작
#상하좌우 델타배열
delta = [[0,-1],[0,1],[-1,0],[1,0]]
dictionary를 만들어서 최초 미생물 정보를 모두 저장하고.. 시뮬레이션을 수행한다
for _ in range(m): ##m시간만 돌면 되니까
#이동 후에 배치되는 맵
after_maps = {}
##이제는 n*n 배열을 순회하는게 아니라 dictionary만 순회하면 이동하지 않은 미생물을 찾을 수 있다
for (x,y),(c,d,max_c) in before_maps.items(): #좌표, 미생물 정보를 나누어서 unpack
##이동할 좌표 구하기
dx = x + delta[d-1][0]
dy = y + delta[d-1][1]
m시간만 돌면 되니까 for _ in range(m)으로 반복문 돌고
after_maps = {}은 매 반복문마다 만들어서 before_maps에서 이동한 미생물 정보를 저장할거고
before_maps.items()를 돌면 좌표, 정보를 같이 빼올 수 있겠지
d를 이용해서 이동한 좌표 dx,dy를 구하고
그리고 여기서 위에서 설명했지만 미생물 군집이 이동할 수 있기 때문에 c와 max_c는 서로 다른거라고
##이제는 map에 배치하는 것이 아니라 0,1,미생물이 존재로 나눌 수는 없다
##하지만 좌표만 알면 약품이 존재하는지 아닌지는 알 수 있다
##그런데 미생물이 결합하는 위치는 약품이 존재하는 곳에서는 절대로 불가능하다
##이동한 위치에 약품이 존재한다면..
if dx == 0 or dx == n-1 or dy == 0 or dy == n-1:
c = c//2 #미생물 절반 소멸시키고
if c != 0: ##미생물이 존재한다면...
d = change_dir[d] #방향을 바꾸고
after_maps[(dx,dy)] = (c,d,c) #이동후 배치하는 map에 저장
이제는 n*n 배열인 이차원 배열에서 이동하는게 아니기 때문에 0아니면 1을 검사할 필요도 없다
이동을 했더니 약품이 존재하냐 존재하지 않느냐로 생각할 수 있다
그리고 약품이 존재하면.. 그 자리는 미생물이 절대로 결합할 수는 없다
그렇기 때문에 이동한 좌표를 이용해서 dx가 0이나 n-1이거나, dy가 0이나 n-1이면 약품이 있는곳에 이동한거고
그런 경우에 미생물 절반을 소멸시켜서 방향을 바꾸고 after_maps에 배치하거나, 0이 되면 소멸시켜서 after_maps에 넣지말거나
그런데 약품이 아닌 곳에 이동했다면??
else: #약품이 존재하지 않는다면...
## 약품이 존재하지 않는 위치에는 미생물이 존재하거나, 존재하지 않거나
##이동했던 미생물이 존재하거나, 이동하지 않은 미생물이 존재하거나, 아무런 미생물도 존재하지 않거나
##하지만 이동후와 이동하기 전을 따로 관리하므로, 애초에 서로 영향을 주지 않기때문에 이동하지 않은 미생물이 존재하는지는 고려할 필요없다
if (dx,dy) in after_maps.keys(): #이동한 위치에 이동했던 미생물이 존재한다면...
##결합과정을 거쳐야함
old_c, old_d, old_max = after_maps[(dx,dy)]
if old_max < c: #존재했던 미생물 군집들 중 미생물 수의 최댓값보다 새로 들어온 미생물의 수가 더 크다면
old_max = c ##최댓값을 갱신하고
old_d = d ##방향도 더 많은 미생물을 가진 미생물 군집 방향으로 갱신하고
old_c += c ##미생물 수를 늘리고
after_maps[(dx,dy)] = (old_c,old_d,old_max) ##미생물 배치
else: ##이동한 곳에 이동했던 미생물이 존재하지 않는다면
after_maps[(dx,dy)] = (c,d,c) ##그냥 이동만 시키면 된다
before_maps = after_maps #다음 시간으로 넘어가기 전에 맵 초기화
약품이 아닌 곳에 이동했다면, 미생물이 존재하는 곳이거나 그렇지 않거나
미생물이 존재하는 곳이라면 after_maps의 key를 검사하면 된다
미생물이 존재하는 곳에 이동했다면 after_maps의 key에 좌표가 존재할 것이다
after_maps의 key에 존재한다면.. 위에서 수행했었던 결합단계를 수행시킨 뒤에 after_maps에 새로 배치하고
그렇지 않다면 그냥 after_maps에 배치하면 끝
그러면 이제 시뮬레이션 1시간이 끝난거다
그리고 before_maps를 after_maps로 초기화 시키고 다음 시뮬레이션을 수행하면 끝
ans = 0
#이제는 미생물 총 수를 셀때 이중 for문을 순회할 필요도 없다
#dict의 value를 순회하면 바로 미생물 수를 얻는다
for (c,d,max_c) in after_maps.values():
ans += c
print('#'+str(tc),ans)
m번 반복하면 after_maps(after_maps={}으로 하기 전에 반복문 끝나니까)나 before_maps에 남아있는 미생물이 존재
이러면 n*n for문을 순회하는 것도 아니고 dict만 순회하면 미생물 총 수를 바로 구할 수 있다는 장점도 있다
여기까지가 시뮬레이션의 기본기이다.
#이제는 맵에 배치하지도 말아
#약품의 위치는 미생물의 좌표만 알면 바로 알 수 있어
#미생물의 정보를 좌표만 넣으면 바로 알 수 있게 dictionary에 따로 관리
#그러면 n*n 이중 for문 순회하는것도 제거가 될것
T = int(input())
for tc in range(1,T+1):
n,m,k = map(int,input().split())
before_maps = {}
##최초 미생물 배치
for _ in range(k):
y,x,c,d = map(int,input().split())
#좌표를 key로 해서 미생물의 정보를 바로 가져오도록
before_maps[(x,y)] = (c,d,c) ##(x,y)에 모인 미생물 군집의 미생물 수의 총합, 움직이는 방향, 군집에 모인 미생물 종류별로 가지는 미생물 수 중 가장 큰 미생물 수
#약품에 위치하면 바꿔야할 방향
#상 > 하, 하> 상, 좌> 우, 우>좌
change_dir = {1:2, 2:1, 3:4, 4:3}
#시뮬레이션 시작
#상하좌우 델타배열
delta = [[0,-1],[0,1],[-1,0],[1,0]]
for _ in range(m): ##m시간만 돌면 되니까
#이동 후에 배치되는 맵
after_maps = {}
##이제는 n*n 배열을 순회하는게 아니라 dictionary만 순회하면 이동하지 않은 미생물을 찾을 수 있다
for (x,y),(c,d,max_c) in before_maps.items(): #좌표, 미생물 정보를 나누어서 unpack
##이동할 좌표 구하기
dx = x + delta[d-1][0]
dy = y + delta[d-1][1]
##이제는 map에 배치하는 것이 아니라 0,1,미생물이 존재로 나눌 수는 없다
##하지만 좌표만 알면 약품이 존재하는지 아닌지는 알 수 있다
##그런데 미생물이 결합하는 위치는 약품이 존재하는 곳에서는 절대로 불가능하다
##이동한 위치에 약품이 존재한다면..
if dx == 0 or dx == n-1 or dy == 0 or dy == n-1:
c = c//2 #미생물 절반 소멸시키고
if c != 0: ##미생물이 존재한다면...
d = change_dir[d] #방향을 바꾸고
after_maps[(dx,dy)] = (c,d,c) #이동후 배치하는 map에 저장
else: #약품이 존재하지 않는다면...
## 약품이 존재하지 않는 위치에는 미생물이 존재하거나, 존재하지 않거나
##이동했던 미생물이 존재하거나, 이동하지 않은 미생물이 존재하거나, 아무런 미생물도 존재하지 않거나
##하지만 이동후와 이동하기 전을 따로 관리하므로, 애초에 서로 영향을 주지 않기때문에 이동하지 않은 미생물이 존재하는지는 고려할 필요없다
if (dx,dy) in after_maps.keys(): #이동한 위치에 이동했던 미생물이 존재한다면...
##결합과정을 거쳐야함
old_c, old_d, old_max = after_maps[(dx,dy)]
if old_max < c: #존재했던 미생물 군집들 중 미생물 수의 최댓값보다 새로 들어온 미생물의 수가 더 크다면
old_max = c ##최댓값을 갱신하고
old_d = d ##방향도 더 많은 미생물을 가진 미생물 군집 방향으로 갱신하고
old_c += c ##미생물 수를 늘리고
after_maps[(dx,dy)] = (old_c,old_d,old_max) ##미생물 배치
else: ##이동한 곳에 이동했던 미생물이 존재하지 않는다면
after_maps[(dx,dy)] = (c,d,c) ##그냥 이동만 시키면 된다
before_maps = after_maps #다음 시간으로 넘어가기 전에 맵 초기화
ans = 0
#이제는 미생물 총 수를 셀때 이중 for문을 순회할 필요도 없다
#dict의 value를 순회하면 바로 미생물 수를 얻는다
for (c,d,max_c) in after_maps.values():
ans += c
print('#'+str(tc),ans)
6. 되돌아보기
마지막 풀이를 잘 기억해두면 어딘가에 쓸모가 있겠지? 시뮬레이션의 기본 틀이라고 생각하고 머리에 담아두자
dictionary로 위치를 key로 정보를 value로 관리하고
시뮬레이션 전과 시뮬레이션 후 dictionary를 따로 관리시키고
최댓값 정보인 max_c를 저장해두는 아이디어는 이런 문제에만 적용되는거긴 할텐데.. 기억해둔다면 결합단계를 제거할 수 있다는거에 유용하겠지
요구하는대로 시뮬레이션을 결국에 성공시킨건 분명 잘했다
그런데.. 이제 눈에 빠지게 고생했던 이유중에 컸던게
continue를 남발한게 문제였지
코드가 너무 기니까 continue에 의해 생략되어버린 로직이 있는데도 못찾아가지고... 분명히 맞는데 자꾸 틀려서 못찾는 경우 생겼지
continue 쓸때 다시한번 주의해야할거고
그리고 최댓값 정보를 저장할때 놓쳤던 사소한 디테일인
c와 max_c는 다르다.. 처음에는 당연히 미생물 하나만 모인거니까 c와 max_c가 같은건데
m번 반복하다보면 여러 미생물이 모여있는 상태에서 움직이니 c와 max_c는 다른거였지.. 생각하면서 했다면 놓치지 않았을거다
'알고리즘 > 구현,시뮬레이션' 카테고리의 다른 글
| 조금 더 어려운 시뮬레이션 연습하기 -미세먼지 안녕!- (0) | 2022.11.08 |
|---|---|
| deque도 인덱스로 접근해서 원소 수정이 가능하다 -컨베이어 벨트 위의 로봇- (0) | 2022.11.07 |
| 성실하게 시뮬레이션 구현하기.. -로봇 청소기- (0) | 2022.11.03 |
| 0.x초 단위로 시뮬레이션하는 방법 -원자소멸시뮬레이션- (0) | 2022.10.30 |
| deque를 이용하면 회전이 가능하다 -보물상자 비밀번호- (0) | 2022.09.21 |
