Baekjoon Online Judge

algorithm practice

- 단계별 문제풀기

30. 최소 신장 트리

최소 비용으로 그래프의 모든 정점을 연결해 봅시다.

Java / Python

5. 행성 터널

2887번

문제의 특성을 활용하여 고려할 간선의 개수를 줄임으로써 푸는 문제

이번 문제는 터널을 총 N-1개 건설해서 모든 행성이 서로 연결되게 하려고 할 때, 모든 행성을 터널로 연결하는데 필요한 최소 비용을 구하는 프로그램을 작성하는 문제이다.

최소 신장 트리 유형 문제이다. 크루스칼 알고리즘을 사용하여 풀 수 있다. 간선들의 리스트를 만들기 위해 행성 간의 거리를 계산한다. 그 후,오름차순으로 간선들을 정렬해준다. 간선과 연결된 두 노드의 부모를 비교하여 다를 경우에만 두 노드를 연결한다.

parent를 자기 자신으로 초기화하고, 부모를 찾는 함수 find와 합집합 연산을 해, 같은 부모를 가지도록 하는 union함수를 이용한다.

• Java

Point class : 번호, x 좌표, y 좌표, z 좌표 저장
Edge class : 간선의 정보를 저장, 연결된 노드 s, e와 비용 저장

import java.io.*;
import java.util.*;

public class Main {

	static class Point {
		int number;
		int x, y, z;

		Point(int number, int x, int y, int z) {
			this.number = number;
			this.x = x;
			this.y = y;
			this.z = z;
		}
	}

	static class Edge implements Comparable<Edge> {
		int s, e;
		int cost;

		Edge(int s, int e, int cost) {
			this.s = s;
			this.e = e;
			this.cost = cost;
		}

		@Override
		public int compareTo(Edge o) {
			// Comparable을 통해 정렬 우선순위 (cost 기준)
			return cost - o.cost;
		}
	}

	static int[] parent;
	static ArrayList<Edge> edgeList;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;

		int N = Integer.parseInt(br.readLine());
		int result = 0;
		edgeList = new ArrayList<>();

		parent = new int[N + 1];
		for (int i = 0; i <= N; i++) {
			parent[i] = i;
		}

		Point[] points = new Point[N];
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());

			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			int z = Integer.parseInt(st.nextToken());

			points[i] = new Point(i, x, y, z);
		}

		// x, y, z에 대해 정렬

		Arrays.sort(points, (p1, p2) -> p1.x - p2.x);
		for (int i = 0; i < N - 1; i++) {
			int cost = Math.abs(points[i].x - points[i + 1].x);
			// 각 행성의 번호와 비용 edgeList에 추가
			edgeList.add(new Edge(points[i].number, points[i + 1].number, cost));
		}

		Arrays.sort(points, (p1, p2) -> p1.y - p2.y);
		for (int i = 0; i < N - 1; i++) {
			int cost = Math.abs(points[i].y - points[i + 1].y);

			edgeList.add(new Edge(points[i].number, points[i + 1].number, cost));
		}

		Arrays.sort(points, (p1, p2) -> p1.z - p2.z);
		for (int i = 0; i < N - 1; i++) {
			int cost = Math.abs(points[i].z - points[i + 1].z);

			edgeList.add(new Edge(points[i].number, points[i + 1].number, cost));
		}

		Collections.sort(edgeList);

		for (int i = 0; i < edgeList.size(); i++) {
			Edge edge = edgeList.get(i);
			if (find(edge.s) != find(edge.e)) {
				result += edge.cost;
				union(edge.s, edge.e);
			}
		}

		bw.write(result + "\n");
		bw.flush();
		bw.close();
		br.close();
	}

	// x의 부모 찾기
	public static int find(int x) {
		if (x == parent[x])
			return x;

		return parent[x] = find(parent[x]);
	}

	// y 부모를 x 부모로 치환하기 (x > y 일 경우 반대)
	public static void union(int x, int y) {
		x = find(x);
		y = find(y);

		if (x != y) {
			if (x < y) {
				parent[y] = x;
			} else {
				parent[x] = y;
			}
		}
	}
}

• Python

import sys
import math
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

# 크루스칼 알고리즘
def find(x):
    if x == parent[x]:
        return x
    parent[x] = find(parent[x]) # 부모 테이블 갱신
    return parent[x]

def union(x, y): 
    x = find(x) 
    y = find(y)

    if x == y: # 동일한 집합일 경우
        return

    if x < y:
        parent[y] = x 
    else: 
        parent[x] = y

N = int(input())
point = [] 
parent = [i for i in range(N+1)]
edges = []
result = 0
cnt = 0

for i in range(N):
    x, y, z = map(int, input().split())
    point.append([x, y, z, i])

# x, y, z 별로 정렬
for i in range(3):
    point.sort(key=lambda x:x[i])#각 좌표별로 정렬
    now_p = point[0][3]
    for j in range(1, N):
        # 간선 구하기
        new_p = point[j][3]
        edges.append([abs(point[j][i]-point[j-1][i]),now_p,new_p])
        now_p = new_p

edges.sort(key = lambda x : x[0])

for e in edges:
    cost, x, y = e
    if find(x) != find(y):
        union(x, y)
        result += cost
    if cnt == N-1:
        break

print(result)