Q44. 행성 터널
🐣문제
때는 2040년, 이민혁은 우주에 자신만의 왕국을 만들었다. 왕국은 N개의 행성으로 이루어져 있다. 민혁이는 이 행성을 효율적으로 지배하기 위해서 행성을 연결하는 터널을 만들려고 한다.
행성은 3차원 좌표위의 한 점으로 생각하면 된다. 두 행성 A(xA, yA, zA)와 B(xB, yB, zB)를 터널로 연결할 때 드는 비용은 min(|xA-xB|, |yA-yB|, |zA-zB|)이다.
민혁이는 터널을 총 N-1개 건설해서 모든 행성이 서로 연결되게 하려고 한다. 이때, 모든 행성을 터널로 연결하는데 필요한 최소 비용을 구하는 프로그램을 작성하시오.
백준 링크 | https://www.acmicpc.net/problem/2887
🐥풀이
최소 비용으로 행성들을 연결한다. 크루스칼 알고리즘을 활용해야 한다.
아주 단순히!! 앗 그냥 거리 경우의 수 모두 구해서 크루스칼 돌리면 되는 것 아냐?! 하고
for p in list(combinations(planet, 2)): p1, p2 = p # 행성1, 행성2, 거리비용 roads.append([p1[3], p2[3], min(abs(p1[0]-p2[0]), abs(p1[1]-p2[1]), abs(p1[2]-p2[2]))])위와 같이 가능한 모든 거리 비용(같은 경로라면 최소 비용으로)을 리스트에 저장하고, 크루스칼을 돌렸다..! (안된다.)
^^... 처참한 메모리 초과 오류 😥
행성의 수가 100,000개까지 갈 수 있다보니 거리의 경우의 수가 너무 많아져서 메모리 오류가 뜬 것 같다. 그럼.. 어떻게 줄여 ㅠㅠㅠ
개인적으로 정말 신기하다고 생각했는데, 최소일 수 있는 후보 경로만을 리스트에 저장하는 것이었다. (댑악) 그럼 메모리 수도 줄일 수 있고, 크루스칼을 사용하면 시간 초과도 안 뜬다 ^__^for i in range(3): # 좌표별로 정렬 (가장 가까운 행성끼리 모아두기) planet = sorted(planet, key=lambda x:x[i]) for j in range(1,n): roads.append([planet[j-1][3], planet[j][3], abs(planet[j-1][i]-planet[j][i])])좌표별로 정리해서, 가까운 행성들끼리의 거리 정보만을 저장한다. 당연히, 좌표가 비슷한 애들끼리 거리도 가까울테니.. (우왕) (여기서 x[0]은 x좌표, x[1]은 y좌표, x[2]는 z좌표 정보를 담고 있다.) xyz 좌표별로 가깝이 예상 친구들을 리스트로 저장해두고-!
# 거리비용 기준으로 정렬 roads = sorted(roads, key=lambda x:x[2])(당연히) 거리비용을 기준으로 오름차순 정렬하여 크루스칼 돌린다! 그럼 완성!! (야호)
크루스칼 돌려서 구한 최소 비용을 출력하면 끝이다 ^!^
🐓코드
# 입력값
n = int(input())
planet, roads, result = [], [], []
for i in range(n):
x, y, z = map(int, input().split())
planet.append([x,y,z,i])
# 가까운 거리 후보들 모아두기
for i in range(3):
# 좌표별로 정렬 (가장 가까운 행성끼리 모아두기)
planet = sorted(planet, key=lambda x:x[i])
for j in range(1,n):
roads.append([planet[j-1][3], planet[j][3], abs(planet[j-1][i]-planet[j][i])])
# 거리비용 기준으로 정렬
roads = sorted(roads, key=lambda x:x[2])
# 팀 초기화
team = [i for i in range(n)]
# 루트 확인
def check_team(team, x):
if team[x]!=x:
return check_team(team,team[x])
return team[x]
# 집합 통일
def union_team(team, a, b):
a, b = check_team(team, a), check_team(team, b)
if a>b:
team[a]=b
else:
team[b]=a
# 크루스칼
for road in roads:
a, b, c = road
if check_team(team, a)!=check_team(team,b):
union_team(team, a, b)
result.append(c)
# 총 최소 비용 출력
print(sum(result))⭐2022.05.12
거리 후보를 정하는 아이디어가 너무 신기해서 코테 공부보다는 그냥 신기하게 공부할 수 있었던 문제였던 것 같다 :)
