행성 터널 (백준 2997번)

https://www.acmicpc.net/problem/2887

2887번: 행성 터널

 

 

이 문제는 크루스칼 알고리즘을 사용해서 행성들간에 터널을 연결 했을 때 드는 최소 비용을 구하면된다. 크루스칼 알고리즘은 그래프 내의 모든 정점들을 가장 적은 비용으로 연결해야 할 때 사용할 수 있다.

 

기본 접근 방법은 모든 행성간의 터널 비용을 구하고 가장 비용이 적은 순으로 연결해나가면서 그 터널에 순환이 있는지 없는지 체크하면 된다.

import sys

n = int(sys.stdin.readline().rstrip())
data = []

# 유니온 파인드(두 정점이 연결됐는가 찾아내는 알고리즘)
parent = [i for i in range(n)]

# 정점 v의 부모를 찾아준다.
def find(v):
    if parent[v] == v:
        return v
    
    # 경로 압축, 루트를 부모로 둔다.
    parent[v] = find(parent[v])
    return parent[v]

def merge(v1, v2):
    v1 = find(v1)
    v2 = find(v2)

    # 부모가 같으면 연결 돼 있다는 의미.
    if v1 == v2:
        return
    # 정점번호가 작은 쪽이 큰 쪽에 붙는다. (이건 마음대로..)
    if v1 < v2:
        parent[v2] = parent[v1]
    else:
        parent[v1] = parent[v2]
    
for i in range(n):
    x, y, z = map(int, sys.stdin.readline().split())
    data.append((x, y, z))

edges = []

# 행성들간 간선의 비용찾기
for i in range(n):
    for j in range(n):
        if i != j:
            cost = min(abs(data[i][0]-data[j][0]),
                abs(data[i][1]-data[j][1]), abs(data[i][2]-data[j][2]))  
            edges.append((i, j, cost))
            
# 적은 비용을 우선적으로 연결해주기 위해 비용을 기준으로 오름차순 정렬을 해준다.       
edges.sort(key=lambda x:x[2])

res = 0
for i, j, c in edges:
    if find(i) != find(j):
        merge(i, j)
        res += c
print(res)

 

 

하지만 이렇게 문제를 제출하면 7% 구간에서 메모리 초과가 발생한다.

기본적으로 임의의 두 정점 사이에 터널을 연결할 수 있다고 가정하므로, 간선의 개수는 N(N-1)/2 개가 될것이다. N이 최대 100,000이라는 조건을 감안하면 매우 큰 수이기에, 한 간선당 3번의 abs 함수 호출과 모든 간선들을 구하는 등의 문제로 메모리 초과가 난듯하다.

 

따라서 최적화가 필요했다.

 

각 정점에는 x, y, z 세개의 행성 좌표가 있고 행성간의 거리는 각 행성의 같은 축의 좌표의 차중에서 제일 작은수가 거리가 된다. 따라서 행성들간의 거리는y축, z축을 배제하고 x좌표들로 이루어진 간선만으로도 최소 신장 트리를 만들 수 있다. 그렇게 서로 다른 행성의 x축은 x축끼리의 간선 비용, y축은 y축.. 이렇게 구한 간선들의 비용으로 최소 신장트리를 만들면 고려해야 할 간선의 수가 3* (N-1)개가 된다.

 

그렇게 구한 비용들로 크루스칼 알고리즘을 적용하면 최소 스패닝 트리를 구할 수 있다.

 

import sys

n = int(sys.stdin.readline().rstrip())
data = []

# 유니온 파인드(두 정점이 연결됐는가 찾아내는 알고리즘)
parent = [i for i in range(n)]

# 정점 v의 부모를 찾아준다.
def find(v):
    if parent[v] == v:
        return v
    
    # 경로 압축, 루트를 부모로 둔다.
    parent[v] = find(parent[v])
    return parent[v]

def merge(v1, v2):
    v1 = find(v1)
    v2 = find(v2)

    # 부모가 같으면 연결 돼 있다는 의미.
    if v1 == v2:
        return
    # 정점번호가 작은 쪽이 큰 쪽에 붙는다. (이건 마음대로..)
    if v1 < v2:
        parent[v2] = parent[v1]
    else:
        parent[v1] = parent[v2]
x = []
y = []
z = []

for i in range(n):
    a, b, c = map(int, sys.stdin.readline().split())
    x.append((a, i))
    y.append((b, i))
    z.append((c, i))

edges = []

x.sort()
y.sort()
z.sort()

# 간선수는 n-1개이고 비용, 정점 순으로 저장
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()
res = 0
for c, i, j in edges:
    if find(i) != find(j):
        merge(i, j)
        res += c
print(res)