[백준] 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)

1. 좌표 x, y, z를 입력 받아 dots 리스트에 넣는다.
2. 양방향 간선이므로 노드 번호가 낮은 순서대로 graph에 간선 정보를 집어넣는다.
3. 가중치를 기준으로 정렬하여 크루스칼 알고리즘을 적용시킨다.

단, 이렇게 해결할 시 메모리 초과가 난다.

위의 코드는 구할 수 있는 모든 간선의 정보를 저장하기 때문이다. 그래서 핵심은 간선을 최소한으로 저장해야만 한다.

모든 간선이 아닌 좌표별로 거리를 구하면 간선의 개수를 현저히 줄일 수 있다. 기존 방식은 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])

1. 처음에 dots에 정보를 넣을 때 현재 노드가 몇번이지를 i로 저장한다.
2. 각 좌표별로 정렬시킨 후 절댓값 거리를 구한다.
3. 좌표별로 구한 절댓값 거리를 기준으로(첫번째 인덱스) 크루스칼 알고리즘을 적용시킨다.