[백준] 2887 행성 터널 - MST
[백준] 2887번 - MST
문제 출처 : https://www.acmicpc.net/problem/2887
크루스칼 알고리즘을 사용해 해결할 수 있는 최소신장트리 유형의 문제이다.
출발 노드, 도착 노드, 가중치로 입력이 주어지는 것이 아니라 3차원 좌표로 주어지는 점에서 흥미로운 문제라고 생각되어 정리해보고자 한다.
실제로 문제를 해결할 때, 이 좌표들로 리스트를 구성할 때 메모리 초과로 한번에 해결하지 못했다.
기존 풀이법
import sys
input = sys.stdin.readline
def Union(x,y):
x = p[x]
y = p[y]
if x!=y:
p[y]=p[x]
def Find(x):
if p[x] == x:
return x
else:
y = Find(p[x])
p[x] = y
return y
N = int(input())
dots = []
p = [i for i in range(N)]
graph = []
ans = 0
for i in range(N):
x, y, z = map(int, input().split())
dots.append([x,y,z])
for i in range(N-1):
for j in range(i,N):
if i==j:
continue
dis = min(abs(dots[i][0]-dots[j][0]), abs(dots[i][1]-dots[j][1]), abs(dots[i][2]-dots[j][2]))
graph.append([dis,i,j])
graph.sort(key = lambda x:x[0])
for w,u,v in graph:
if Find(u) == Find(v):
continue
Union(u,v)
ans+=w
print(ans)
- 좌표 x, y, z를 입력 받아 dots 리스트에 넣는다.
- 양방향 간선이므로 노드 번호가 낮은 순서대로 graph에 간선 정보를 집어넣는다.
- 가중치를 기준으로 정렬하여 크루스칼 알고리즘을 적용시킨다.
단, 이렇게 해결할 시 메모리 초과가 난다.
위의 코드는 구할 수 있는 모든 간선의 정보를 저장하기 때문이다. 그래서 핵심은 간선을 최소한으로 저장해야만 한다.
모든 간선이 아닌 좌표별로 거리를 구하면 간선의 개수를 현저히 줄일 수 있다. 기존 방식은 V(V-1)/2의 갯수를 구하지만, 좌표별로 구할 시 3(V-1)개만 구하면 된다.
for i in range(N):
x, y, z = map(int, input().split())
dots.append([x,y,z,i])
for j in range(3):
dots.sort(key=lambda x:x[j])#각 좌표별로 정렬
before_location=dots[0][3]
for i in range(1,N):#각 좌표별로 간선추가
cur_location=dots[i][3]
graph.append([abs(dots[i][j]-dots[i-1][j]),before_location,cur_location])
before_location=cur_location
graph.sort(key = lambda x:x[0])
- 처음에 dots에 정보를 넣을 때 현재 노드가 몇번이지를 i로 저장한다.
- 각 좌표별로 정렬시킨 후 절댓값 거리를 구한다.
- 좌표별로 구한 절댓값 거리를 기준으로(첫번째 인덱스) 크루스칼 알고리즘을 적용시킨다.
Author And Source
이 문제에 관하여([백준] 2887 행성 터널 - MST), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@seho100/백준-2887-행성-터널-MST저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)