문제
최소 연결문제구만 (최소신장트리)
풀이
풀이아이디어
최소신장트리 만들기 = 크루스칼
- 크루스칼 알고리즘
- 시간복잡도 : 간선갯수 E일때
- 아이디어 : 각 정점 간 간선의 가중치를 작은 순서대로 선택해 나가는데, union-find 연산으로 싸이클이 발생하는지 여부를 판단하면서 선택하는 것
이 문제에 있어서
- 임의의 두 노드 사이에 터널을 연결한다고 함
- 모든 행성들 간에 서로 X, Y, Z 좌표값 차이를 구해서 간선의 가중치 정보로 넣는 경우를 생각 할 수 있다.
- 간선의 갯수는 N(N-1)/2 개
- 이 경우 이 문제에서는 행성이 최대 10만개 주어지므로 대략 10만*10만 만큼의 비교 및 데이터가 발생. 따라서 메모리 초과 가능
- 따라서 간선의 후보를 적절히 설정해야한다.
- x, y, z 축을 사용하고 있다.
- x,y,z좌표 중에서 거리가 짧은것 하나만 가중치가 된다. 또한, 모든 행성을 후보로 연결할 필요 없이 x,y,z 좌표중 행성 가까이에 있는 행성들만 후보터널로 사용하면된다.
- 모든 각각의 축에 대하여 정렬 이후 -> 각각 N-1개의 간선을 고려해도 최적의 솔루션을 찾을 수 있다.
- 따라서, 고려하는 총 간선의 갯수는 3*(N-1)
(제한시간 내 해결 가능 )
구현 아이디어 그림
정리
크루스칼 자체를 구현하기보다,
크루스칼을 구현하는데 필요한 edge의 후보가 여러가지이고, 그 후보중에서 진짜 edge를 제한안에 구하는 것이 중요한 문제구만
코드
# 특정 원소가 속한 집합을 찾기
def find_parent(parent, x) :
#루트 노드가 아니면, 루트 노드를 찾을때까지 재귀적으로 호출
if parent[x] != x :
parent[x] = find_parent(parent, parent[x])
return parent[x]
# 두 원소가 속한 집합을 합치기
def union_parent(parent, a, b) :
a = find_parent(parent, a)
b = find_parent(parent, b)
if a < b :
parent[b] = a
else :
parent[a] = b
n = int(input()) # 노드의 갯수 입력받기
parent = [0] * (n+1) # 부모 테이블 초기화
edges = [] # 모든 간선을 담을 리스트
result = 0 # 최종 비용을 담을 변수
# 부모 테이블상에서, 부모를 자기 자신으로 초기화
for i in range(1, n+1) :
parent[i] = i
x = []
y = []
z = []
# 모든 노드에 대한 좌표 값 입력받기
for i in range(1, n+1) :
data = list(map(int, input().split()))
x.append((data[0], i))
y.append((data[1], i))
z.append((data[2], i))
x.sort()
y.sort()
z.sort()
# 인접한 노드들로부터 간선 정보를 추출하여 처리
for i in range(n-1) :
# 비용순으로 정렬하기 위해서 튜플의 첫번째 원소를 비용으로 ㅓㅅㄹ정
edges.append((x[i+1][0] - x[i][0], x[i][1], x[i+1][1]))
edges.append((y[i+1][0] - y[i][0], y[i][1], y[i+1][1]))
edges.append((z[i+1][0] - z[i][0], z[i][1], z[i+1][1]))
# 간선을 비용순으로 정렬
edges.sort()
# 간선을 하나씩 확인하여
for edge in edges :
cost, a, b = edge
# 사이클이 발생하지 않는 경우에만 집합에 포함
if find_parent(parent, a) != find_parent(parent, b) :
union_parent(parent, a, b)
result += cost
print(result)
레퍼런스
Sometimes you win, sometimes you learn 🏃♀️