문제
왕국은 N개의 행성으로 이루어져 있다. 행성은 3차원 좌표의 한 점으로, 두 행성을 터널로 연결할 때 드는 비용은 min(abs(xa-xb),abs(ya-yb),abs(za-zb))이다.
민혁이는 터널을 총 N-1개 건설해서 모든 행성이 서로 연결되게 하려고 한다. 이때, 모든 행성을 터널로 연결하는데 필요한 최소 비용을 구하는 프로그램을 작성하시오
입력
첫째 줄에 행성의 개수 N이 주어진다 (1<=N<=100,000)
다음 N개의 줄에는 각 행성의 x, y, z 좌표가 주어진다.
출력
첫째 줄에 모든 행성을 터널로 연결하는데 필요한 최소 비용을 출력한다.
이 문제의 시간 제한은 1초이고, 입력 값은 최대 100,000개 이므로
O(n^2)으로 코드를 짜게 되면 시간 초과가 발생하게 된다.
잘못된 풀이 : 완전 탐색 + 크루스칼 -> 메모리 초과 발생!
import sys
def find_parent(parent, x):
if parent[x] != x:
parent[x] = find_parent(parent, parent[x])
return parent[x]
def union(parent, a, b):
pa = find_parent(parent, a)
pb = find_parent(parent, b)
if pa != pb:
if rank[pa] > rank[pb]: parent[pb] = pa
elif rank[pa] < rank[pb]: parent[pa] = pb
else: parent[pa] = pb; rank[pb] += 1
def combination(arr):
result = []
def generate(chosen):
if len(chosen) == 2:
p1 = chosen[0]; p2 = chosen[1]
result.append((min(abs(p1[1]-p2[1]),abs(p1[2]-p2[2]),abs(p1[3]-p2[3])), p1[0],p2[0]))
return
start = arr.index(chosen[-1])+1 if chosen else 0
for nxt in range(start, len(arr)):
chosen.append(arr[nxt])
generate(chosen)
chosen.pop()
generate([])
return result
n = int(input())
parent = [x for x in range(n+1)]
rank = [0 for x in range(n+1)]; edges = []
for i in range(1,n+1):
x, y, z = map(int,sys.stdin.readline().split())
edges.append((i,x,y,z))
edges = combination(edges); edges.sort()
cost = 0
for e in edges:
if find_parent(parent, e[1]) != find_parent(parent, e[2]):
union(parent, e[1], e[2]); cost += e[0]
print(cost)노드의 개수가 n개인 그래프의 MST를 만들기 위해서는 n-1개의 간선만 있으면 된다!
그러므로 간선을(노드값의 차) x 크기 순으로 정렬 했을 때 순위가 n등 이하인 간선은 mst에 사용될 가능성이 없으므로 제외시켜도 된다.
마찬가지로 y와 z를 기준으로 정렬했을 대 n등 이하인 간선들은 제외 시켜도 된다.
x 기준 상위 n등 이내, y 기준 상위 n등 이내, z 기준 상위 n등 이내의 값들을 얻고 싶으면, 간선들을 x, y, z 각각을 기준으로 한 번씩 정렬한 후에 상위 3*n등 이내의 값들을 보면된다.
다음 그림과 같이 최악으로 극단적인 상황에서도 각 기준의 상위권 n등은 최종 3*n등 안에 들어있게 된다!
그러므로 각 기준 상위 n등이내 원소들은 적어도 최종 3*n등 이내에 들어있게 된다!
n^2의 메모리 공간을 사용할 경우 메모리 초과가 발생하기 때문에
간선들을 탐색하며 슬라이딩 윈도우 기법을 활용해야 한다!
1) 힙의 크기가 3*n보다 작을 경우 그냥 집어 넣고
2) 힙의 크기가 3*n보다 클 경우 집어 넣은 후 크기가 가장 큰 간선을 뱉어낸다.
슬라이딩 윈도우 기법을 적용하면서 메모리 초과 없앨 수 있지만,
입력값이 최대 100,000개 이므로 간선 탐색을 이중 for문으로 실시하게 되면 시간 복잡도가 O(n^2)이 되어 시간 초과가 발생하게 된다!
x값을 기준으로 정렬하게 되었을 때
순서대로 1번,2번,3번,4번,5번이라 하자.
1->2는 1->3, 1->4, 1->5 보다 작거나 같을 수 밖에 없다.
2->3도 2->4, 2->5 보다 작거나 같을 수 밖에 없다.
3과 4도 마찬가지다.
그러므로 for문을 한 번만 돌면서 1칸차이만 비교하면 된다.
그러면 이런 의문이 들 수도 있다.
3->4(1칸)가 1->3(2칸)보다 클 수도 있지 않나?
1->3(2칸)은 1->2 + 2->3과 같다.
(즉, 1->2와 2->3은 1->3보다 반드시 작거나 같다)
만약 edges에 1->3이 3->4보다 작아서 1->3이 대신하여 들어갔다 치더라도 1과 2가 union, 2와 3이 union된 후므로 크루스칼 알고리즘에서 걸러지게 된다!!!
이렇게 하면 시간 초과 문제도 해결할 수 있다!
올바른 풀이 : 슬라이딩 윈도우 + 1칸 단위로 + 크루스칼
import sys
from heapq import heappush, heappop
def find_parent(parent, x):
if parent[x] != x:
parent[x] = find_parent(parent, parent[x])
return parent[x]
def union(parent, a, b):
pa = find_parent(parent, a)
pb = find_parent(parent, b)
if pa != pb:
if rank[pa] > rank[pb]: parent[pb] = pa
elif rank[pa] < rank[pb]: parent[pa] = pb
else: parent[pa] = pb; rank[pb] += 1
n = int(input())
parent = [x for x in range(n+1)]
rank = [0 for x in range(n+1)]
planets = []; edges = []
for i in range(1,n+1):
x, y, z = map(int,sys.stdin.readline().split())
planets.append((i,x,y,z))
for k in range(1,4):
planets.sort(key=lambda x: x[k])
for i in range(n-1):
if len(edges) < 3*n:
heappush(edges,(-abs(planets[i][k]-planets[i+1][k]), planets[i][0], planets[i+1][0]))
else:
heappush(edges,(-abs(planets[i][k]-planets[i+1][k]), planets[i][0], planets[i+1][0]))
heappop(edges)
cost = 0; link = 0
for e in sorted(edges, key=lambda x: -x[0]):
if find_parent(parent, e[1]) != find_parent(parent, e[2]):
# cost가 다른, 같은 노드쌍의 연결이 다시 주어지는 경우 여기에서 걸러짐
union(parent, e[1], e[2]); cost += (-e[0]); link += 1
if link == n-1: break
print(cost)