728x90
반응형
SMALL
진짜 문제를 제대로 읽는 연습부터 해야겠습니다. 정말 ㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠ 1시간을 이상한 곳에서...헤맸습니다.
https://www.codetree.ai/training-field/frequent-problems/problems/virus-experiment/submissions
코드트리 | 코딩테스트 준비를 위한 알고리즘 정석
최고의 알고리즘 전문가들이 체계적인 코딩테스트 문제 유형 분류와 학습 커리큘럼을 제시합니다. 알고리즘 학습의 A to Z를 경험해보세요!
www.codetree.ai
1. 실패 -> 단순히 k 번 진행되어야 하는데 처음에 2로 하드코딩 해놓은 걸 바꾸지 않아서 생겼던 문제였습니다.
2 -> k
import heapq
import copy
n, m, k = map(int, input().split())
add_foods_infos = [list(map(int, input().split())) for _ in range(n)]
virus_locations_info = [list(map(int, input().split())) for _ in range(m)]
virus_graph = [[[] for _ in range(n)] for _ in range(n)]
foods_graph = [[5 for _ in range(n)] for _ in range(n)]
dead_virus = []
for y, x, age in virus_locations_info:
heapq.heappush(virus_graph[y - 1][x - 1], age)
#task1 나이가 어린 바이러스 부터 양분 섭취 -> 양분섭취한 바이러스 나이 + 1 양분이 부족하면 그 즉시 죽음.
def task1():
global virus_graph, n, deads_virus
for y in range(n):
for x in range(n):
newVirus = []
for virus_age in virus_graph[y][x]:
if foods_graph[y][x] - virus_age >= 0:
foods_graph[y][x] -= virus_age #먹이 감소
heapq.heappush(newVirus, virus_age+1) #나이 1추가한 바이러스
else:
heapq.heappush(dead_virus, [y,x,virus_age])
virus_graph[y][x] = newVirus
#task2 모든 바이러스 섭취 후 죽은 바이러스가 양분을오 변함. 죽은 바이러스 마다 나이를 2로 나눈값이 양분으로 추가.
def task2():
global dead_virus, foods_graph
while dead_virus:
y, x, virus_age = heapq.heappop(dead_virus)
foods_graph[y][x] += virus_age // 2
#task3 바이러스 번식 진행 5의 배수의 나이를 가진 바이러스 -> 인접 8개 칸에 나이 1인 바이러스 생김. 그래프 범위 밖 번식 x
def validation(ny, nx):
global n
return 0 <= ny < n and 0 <= nx < n
def task3():
global virus_graph
dy, dx = [-1, -1, 0, 1, 1, 1, 0, -1],[0, 1, 1, 1 ,0, -1, -1, -1]
tmp_virus_graph = virus_graph
for y in range(n):
for x in range(n):
for virus_age in virus_graph[y][x]:
if virus_age % 5 == 0:
for d in range(8):
ny = y + dy[d]
nx = x + dx[d]
if validation(ny, nx):
heapq.heappush(tmp_virus_graph[ny][nx], 1)
virus_graph = tmp_virus_graph
#task4. 1,2,3 이후 주어진 양분의 양에 따라 1 양분이 주어짐
def task4():
global n, foods_graph
for y in range(n):
for x in range(n):
foods_graph[y][x] += 1
for i in range(2):
task1()
task2()
task3()
task4()
total = 0
for y in range(n):
for x in range(n):
total += len(virus_graph[y][x])
print(total)
2. 실패 -> 이것도 virus의 양분이 전체 지도에서 1씩 늘어나는 것이 아니라 처음에 제시해 준 만큼 늘어야하는데, 1로 하드 코딩해놓았던 실수였습니다.
1 -> add_foods_infos[y][x]
import heapq
import copy
n, m, k = map(int, input().split())
add_foods_infos = [list(map(int, input().split())) for _ in range(n)]
virus_locations_info = [list(map(int, input().split())) for _ in range(m)]
virus_graph = [[[] for _ in range(n)] for _ in range(n)]
foods_graph = [[5 for _ in range(n)] for _ in range(n)]
dead_virus = []
for y, x, age in virus_locations_info:
heapq.heappush(virus_graph[y - 1][x - 1], age)
#task1 나이가 어린 바이러스 부터 양분 섭취 -> 양분섭취한 바이러스 나이 + 1 양분이 부족하면 그 즉시 죽음.
def task1():
global virus_graph, n, deads_virus
for y in range(n):
for x in range(n):
newVirus = []
for virus_age in virus_graph[y][x]:
if foods_graph[y][x] - virus_age >= 0:
foods_graph[y][x] -= virus_age #먹이 감소
heapq.heappush(newVirus, virus_age+1) #나이 1추가한 바이러스
else:
heapq.heappush(dead_virus, [y,x,virus_age])
virus_graph[y][x] = newVirus
#task2 모든 바이러스 섭취 후 죽은 바이러스가 양분을오 변함. 죽은 바이러스 마다 나이를 2로 나눈값이 양분으로 추가.
def task2():
global dead_virus, foods_graph
while dead_virus:
y, x, virus_age = heapq.heappop(dead_virus)
foods_graph[y][x] += virus_age // 2
#task3 바이러스 번식 진행 5의 배수의 나이를 가진 바이러스 -> 인접 8개 칸에 나이 1인 바이러스 생김. 그래프 범위 밖 번식 x
def validation(ny, nx):
global n
return 0 <= ny < n and 0 <= nx < n
def task3():
global virus_graph
dy, dx = [-1, -1, 0, 1, 1, 1, 0, -1],[0, 1, 1, 1 ,0, -1, -1, -1]
tmp_virus_graph = virus_graph
for y in range(n):
for x in range(n):
for virus_age in virus_graph[y][x]:
if virus_age % 5 == 0:
for d in range(8):
ny = y + dy[d]
nx = x + dx[d]
if validation(ny, nx):
heapq.heappush(tmp_virus_graph[ny][nx], 1)
virus_graph = tmp_virus_graph
#task4. 1,2,3 이후 주어진 양분의 양에 따라 1 양분이 주어짐
def task4():
global n, foods_graph
for y in range(n):
for x in range(n):
foods_graph[y][x] += 1
for i in range(k):
task1()
task2()
task3()
task4()
total = 0
for y in range(n):
for x in range(n):
total += len(virus_graph[y][x])
print(total)
3. 실패 -> 처음부터 heap 으로 설계하면 안되었습니다. 5의 배수일 때마다 8방향만큼 바이러스 만큼 자식이 생성되기 때문에 숫자가 기하 급수적으로 늘어납니다.
heap 바이러스를 하나 하나 처리 -> dictionary로 묶어 같은 나이의 바이러스를 함께 처리
import heapq
import copy
n, m, k = map(int, input().split())
add_foods_infos = [list(map(int, input().split())) for _ in range(n)]
virus_locations_info = [list(map(int, input().split())) for _ in range(m)]
virus_graph = [[[] for _ in range(n)] for _ in range(n)]
foods_graph = [[5 for _ in range(n)] for _ in range(n)]
dead_virus = []
for y, x, age in virus_locations_info:
heapq.heappush(virus_graph[y - 1][x - 1], age)
#task1 나이가 어린 바이러스 부터 양분 섭취 -> 양분섭취한 바이러스 나이 + 1 양분이 부족하면 그 즉시 죽음.
def task1():
global virus_graph, n, deads_virus
for y in range(n):
for x in range(n):
newVirus = []
while virus_graph[y][x]:
virus_age = heapq.heappop(virus_graph[y][x])
if foods_graph[y][x] - virus_age >= 0:
foods_graph[y][x] -= virus_age #먹이 감소
heapq.heappush(newVirus, virus_age+1) #나이 1추가한 바이러스
else:
heapq.heappush(dead_virus, [y,x,virus_age])
virus_graph[y][x] = newVirus
#task2 모든 바이러스 섭취 후 죽은 바이러스가 양분을오 변함. 죽은 바이러스 마다 나이를 2로 나눈값이 양분으로 추가.
def task2():
global dead_virus, foods_graph
while dead_virus:
y, x, virus_age = heapq.heappop(dead_virus)
foods_graph[y][x] += virus_age // 2
#task3 바이러스 번식 진행 5의 배수의 나이를 가진 바이러스 -> 인접 8개 칸에 나이 1인 바이러스 생김. 그래프 범위 밖 번식 x
def validation(ny, nx):
global n
return 0 <= ny < n and 0 <= nx < n
def task3():
global virus_graph
dy, dx = [-1, -1, 0, 1, 1, 1, 0, -1],[0, 1, 1, 1 ,0, -1, -1, -1]
tmp_virus_graph = copy.deepcopy(virus_graph)
for y in range(n):
for x in range(n):
for virus_age in virus_graph[y][x]:
if virus_age % 5 == 0:
for d in range(8):
ny = y + dy[d]
nx = x + dx[d]
if validation(ny, nx):
heapq.heappush(tmp_virus_graph[ny][nx], 1)
virus_graph = tmp_virus_graph
#task4. 1,2,3 이후 주어진 양분의 양에 따라 1 양분이 주어짐
def task4():
global n, foods_graph
for y in range(n):
for x in range(n):
foods_graph[y][x] += add_foods_infos[y][x]
for i in range(k):
task1()
task2()
task3()
task4()
# for i in virus_graph:
# print(i)
# print()
# for i in foods_graph:
# print(i)
# print()
total = 0
for y in range(n):
for x in range(n):
total += len(virus_graph[y][x])
print(total)
4. 실패 -> 바이러스가 양분이 될 때 소수점이 내림이 되어야하는데...이부분을 착각을 했습니다. 각 개별 바이러스 마다 내림이 되어야하는데 나이를 모두 합쳐 //2 를 했기에 필요이상의 양분이 생겨 바이러스가 요구사항 이상으로 생성되었습니다.
sum(each_virus) // 2 -> sum(each_virus // 2)
import heapq
import copy
from collections import defaultdict
n, m, k = map(int, input().split())
add_foods_infos = [list(map(int, input().split())) for _ in range(n)]
virus_locations_info = [list(map(int, input().split())) for _ in range(m)]
virus_graph = [[defaultdict(int) for _ in range(n)] for _ in range(n)]
foods_graph = [[5 for _ in range(n)] for _ in range(n)]
dead_virus = []
for y, x, age in virus_locations_info:
virus_graph[y - 1][x - 1][age] += 1
#task1 나이가 어린 바이러스 부터 양분 섭취 -> 양분섭취한 바이러스 나이 + 1 양분이 부족하면 그 즉시 죽음.
def task1():
global virus_graph, n, deads_virus
tmp_virus_graph = [[defaultdict(int) for _ in range(n)] for _ in range(n)]
for y in range(n):
for x in range(n):
for virus_age, count in sorted(virus_graph[y][x].items()):
if foods_graph[y][x] - virus_age * count >= 0:
foods_graph[y][x] -= virus_age * count #먹이 감소
tmp_virus_graph[y][x][virus_age + 1] += count #나이 1추가한 바이러스
else:
ate_virus_count = foods_graph[y][x] // virus_age
foods_graph[y][x] -= virus_age * ate_virus_count
if ate_virus_count != 0:
tmp_virus_graph[y][x][virus_age + 1] += ate_virus_count
heapq.heappush(dead_virus, [y,x,virus_age * (count - ate_virus_count)])
virus_graph = tmp_virus_graph
#task2 모든 바이러스 섭취 후 죽은 바이러스가 양분을오 변함. 죽은 바이러스 마다 나이를 2로 나눈값이 양분으로 추가.
def task2():
global dead_virus, foods_graph
while dead_virus:
y, x, virus_age = heapq.heappop(dead_virus)
foods_graph[y][x] += virus_age // 2
#task3 바이러스 번식 진행 5의 배수의 나이를 가진 바이러스 -> 인접 8개 칸에 나이 1인 바이러스 생김. 그래프 범위 밖 번식 x
def validation(ny, nx):
global n
return 0 <= ny < n and 0 <= nx < n
def task3():
global virus_graph
dy, dx = [-1, -1, 0, 1, 1, 1, 0, -1],[0, 1, 1, 1 ,0, -1, -1, -1]
tmp_virus_graph = copy.deepcopy(virus_graph)
for y in range(n):
for x in range(n):
for virus_age, count in sorted(virus_graph[y][x].items()):
if virus_age % 5 == 0:
for d in range(8):
ny = y + dy[d]
nx = x + dx[d]
if validation(ny, nx):
tmp_virus_graph[ny][nx][1] += count
virus_graph = tmp_virus_graph
#task4. 1,2,3 이후 주어진 양분의 양에 따라 1 양분이 주어짐
def task4():
global n, foods_graph
for y in range(n):
for x in range(n):
foods_graph[y][x] += add_foods_infos[y][x]
for i in range(k):
task1()
task2()
task3()
task4()
total = 0
for y in range(n):
for x in range(n):
for i in virus_graph[y][x]:
total += virus_graph[y][x][i]
print(total)5. 성공
import heapq
import copy
from collections import defaultdict
n, m, k = map(int, input().split())
add_foods_infos = [list(map(int, input().split())) for _ in range(n)]
virus_locations_info = [list(map(int, input().split())) for _ in range(m)]
virus_graph = [[defaultdict(int) for _ in range(n)] for _ in range(n)]
foods_graph = [[5 for _ in range(n)] for _ in range(n)]
dead_virus = []
for y, x, age in virus_locations_info:
virus_graph[y - 1][x - 1][age] += 1
#task1 나이가 어린 바이러스 부터 양분 섭취 -> 양분섭취한 바이러스 나이 + 1 양분이 부족하면 그 즉시 죽음.
def task1():
global virus_graph, n, deads_virus
tmp_virus_graph = [[defaultdict(int) for _ in range(n)] for _ in range(n)]
for y in range(n):
for x in range(n):
for virus_age, count in sorted(virus_graph[y][x].items()):
if foods_graph[y][x] - virus_age * count >= 0:
foods_graph[y][x] -= virus_age * count #먹이 감소
tmp_virus_graph[y][x][virus_age + 1] += count #나이 1추가한 바이러스
else:
ate_virus_count = foods_graph[y][x] // virus_age
if ate_virus_count != 0:
tmp_virus_graph[y][x][virus_age + 1] += ate_virus_count
foods_graph[y][x] -= virus_age * ate_virus_count
heapq.heappush(dead_virus, [y,x,(virus_age // 2) * (count - ate_virus_count)])
virus_graph = tmp_virus_graph
#task2 모든 바이러스 섭취 후 죽은 바이러스가 양분을오 변함. 죽은 바이러스 마다 나이를 2로 나눈값이 양분으로 추가.
def task2():
global dead_virus, foods_graph
while dead_virus:
y, x, virus_age = heapq.heappop(dead_virus)
foods_graph[y][x] += virus_age
#task3 바이러스 번식 진행 5의 배수의 나이를 가진 바이러스 -> 인접 8개 칸에 나이 1인 바이러스 생김. 그래프 범위 밖 번식 x
def validation(ny, nx):
global n
return 0 <= ny < n and 0 <= nx < n
def task3():
global virus_graph
dy, dx = [-1, -1, 0, 1, 1, 1, 0, -1],[0, 1, 1, 1 ,0, -1, -1, -1]
tmp_virus_graph = copy.deepcopy(virus_graph)
tmp_sorted_graph = [[defaultdict(int) for _ in range(n)] for _ in range(n)]
for y in range(n):
for x in range(n):
for virus_age, count in sorted(virus_graph[y][x].items()):
if virus_age % 5 == 0:
for d in range(8):
ny = y + dy[d]
nx = x + dx[d]
if validation(ny, nx):
tmp_virus_graph[ny][nx][1] += count
for y in range(n):
for x in range(n):
for virus_age, count in sorted(tmp_virus_graph[y][x].items()):
tmp_sorted_graph[y][x][virus_age] += count
virus_graph = tmp_sorted_graph
#task4. 1,2,3 이후 주어진 양분의 양에 따라 1 양분이 주어짐
def task4():
global n, foods_graph
for y in range(n):
for x in range(n):
foods_graph[y][x] += add_foods_infos[y][x]
for i in range(k):
task1()
task2()
task3()
task4()
total = 0
for y in range(n):
for x in range(n):
for i in virus_graph[y][x]:
total += virus_graph[y][x][i]
print(total)728x90
반응형
LIST
