[알고리즘] BOJ 16398 행성 연결 #Python

[BOJ] 16398 행성 연결 바로가기

📍 문제

홍익 제국의 중심은 행성 T이다. 제국의 황제 윤석이는 행성 T에서 제국을 효과적으로 통치하기 위해서, N개의 행성 간에 플로우를 설치하려고 한다.

두 행성 간에 플로우를 설치하면 제국의 함선과 무역선들은 한 행성에서 다른 행성으로 무시할 수 있을 만큼 짧은 시간만에 이동할 수 있다. 하지만, 치안을 유지하기 위해서 플로우 내에 제국군을 주둔시켜야 한다.

모든 행성 간에 플로우를 설치하고 플로우 내에 제국군을 주둔하면, 제국의 제정이 악화되기 때문에 황제 윤석이는 제국의 모든 행성을 연결하면서 플로우 관리 비용을 최소한으로 하려 한다.

N개의 행성은 정수 1,…,N으로 표시하고, 행성 i와 행성 j사이의 플로우 관리비용은 Cij이며, i = j인 경우 항상 0이다.

제국의 참모인 당신은 제국의 황제 윤석이를 도와 제국 내 모든 행성을 연결하고, 그 유지비용을 최소화하자. 이때 플로우의 설치비용은 무시하기로 한다.

---

📍 입력

입력으로 첫 줄에 행성의 수 N (1 ≤ N ≤ 1000)이 주어진다.

두 번째 줄부터 N+1줄까지 각 행성간의 플로우 관리 비용이 N x N 행렬 (Cij), (1 ≤ i, j ≤ N, 1 ≤ Cij ≤ 100,000,000, Cij = Cji, Cii = 0) 로 주어진다.

---

📍 출력

모든 행성을 연결했을 때, 최소 플로우의 관리비용을 출력한다.

---

📍 풀이

💡 고찰

• 문제를 보자마자 싸이클이 발생하지 않는 최단 거리의 경로부터 추가하여 모든 정점을 최소 비용으로 연결하는 크루스칼(Kruskal) 알고리즘이 생각이 났다.
• union() 과 find() 코드만 복사해와서 코드를 작성했는데 한번에 테스트를 통과할 수 있었다.

📌 문제 풀이

✏️ 1. 간선(edges) 정보 추출

for i in range(N):
    weight = list(map(int,stdin.readline().split()))
    for j in range(i+1,N):
        edges.append((weight[j],i,j))
edges.sort()

🧷 예제 입력2

0 6 8 1 3
6 0 5 7 3
8 5 0 9 4
1 7 9 0 6
3 3 4 6 0

• 문제에서 예시로 주어진 간선 정보를 확인해보면 좌측 상단에서 우측 하단으로 이루어진 대각선을 기준으로 가중치가 대칭을 이루고 있는 것을 확인할 수 있다.
• 이를 통해 양방향 그래프임을 알 수 있다.
• 따라서 대각선 기준 상단의 간선 정보만을 추출하여 edges 배열에 추가하였다.
• 간선 정보를 추출한 후 크루스칼(Kruskal) 알고리즘을 적용하기 위해 간선을 가중치(weight)를 기준으로 오름차순으로 정렬한다.

✏️ 2. Union & Find

def find(x):
    if x != parents[x]:
        parents[x] = find(parents[x])
    return parents[x]
def union(x, y):
    x = find(x)
    y = find(y)
    parents[max(x,y)] = min(x,y)

• 크루스칼(Kruskal) 알고리즘을 적용하기 위해 union() 과 find() 함수를 구현한다.

✏️ 3. 크루스칼(Kruskal) 알고리즘 적용

for w, x, y in edges:
    x, y = find(x), find(y)
    if x == y: continue
    answer += w
    union(x,y)

• 주어진 두 정점(x, y)의 부모 노드를 찾은 후 만약 서로의 부모 노드가 같다면 간선을 연결할 경우 싸이클이 생겨 필요없는 유지비용이 늘어남으로 continue 를 통해 해당 간선은 연결하지 않도록 한다.
• 만약 서로의 부모 노드가 다르다면 간선을 연결해도 싸이클이 생기지 않고 현재 연결할 수 있는 최소 유지비용의 간선이므로 answer에 유지비용을 추가한다.
• 이후 union() 함수를 통해 두 정점을 연결해 준다.

✍ 코드

from sys import stdin

def solution(N,edges):
    answer = 0
    parents = [i for i in range(N+1)]

    # [0] Union & Find
    def find(x):
        if x != parents[x]:
            parents[x] = find(parents[x])
        return parents[x]
    def union(x, y):
        x = find(x)
        y = find(y)
        parents[max(x,y)] = min(x,y)
    
    # [1] Kruskal 알고리즘 적용
    for w, x, y in edges:
        x, y = find(x), find(y)
        if x == y: continue
        answer += w
        union(x,y)
    return answer

edges = []
N = int(stdin.readline())
for i in range(N):
    weight = list(map(int,stdin.readline().split()))
    for j in range(i+1,N):
        edges.append((weight[j],i,j))
edges.sort()

result = solution(N,edges)
print(result)