🚀문제

1774번: 우주신과의 교감
LV : 골드 3

🚀풀이 과정

해당 문제는 최소신장트리(MST)를 만들어야 한다.
MST를 만드는 알고리즘은 크루스칼과 프림 알고리즘이 있는데, 여기에서는 크루스칼 알고리즘을 써보기로 했다.

이 문제가 일반적인 크루스칼 알고리즘과 다른 점은 이미 연결된 간선 정보가 있다는 점이다.

코드 흐름

⭐초기 설정

1) Node 클래스 생성

위치가 x, y 좌표로 나오기 때문에 Node 클래스를 생성해준다.

class Node {
	long x, y;

	public Node(long x, long y) {
		this.x = x;
		this.y = y;
	}
}

2) Edge 클래스 생성

크루스칼 알고리즘을 위해서는 가중치가 적은 간선부터 선택해야 하기 때문에 Comparable을 적용해준다.

class Edge implements Comparable<Edge> {
	int from, to;
	double w;

	public Edge(int from, int to, double w) {
		this.from = from;
		this.to = to;
		this.w = w;
	}

	@Override
	public int compareTo(Edge o) {
		// double 비교 시 오차 문제 때문에 Math.signum()을 사용하는 것이 안전
		return Double.compare(this.w, o.w);
	}
}

⭐크루스칼 알고리즘

1) 초기 설정

// 1. 초기 설정
  parent = new int[N + 1];
  // 부모 배열 초기화
  for (int i = 1; i < N + 1; i++) {
  	parent[i] = i;
  }

2) 좌표값 저장

// 2. 좌표값 저장
List<Node> spots = new ArrayList<>(N + 1);
spots.add(null);// 0번째는 비어두기

for (int i = 0; i < N; i++) {
  st = new StringTokenizer(br.readLine());
  long x = Long.parseLong(st.nextToken());
  long y = Long.parseLong(st.nextToken());

  spots.add(new Node(x, y));
}

3) 이미 연결된 M개의 통로 처리

union-find로 집합을 묶어준다.

int edgesCount = 0; // 선택된 간선의 개수
for (int i = 0; i < M; i++) {
	st = new StringTokenizer(br.readLine());
	int from = Integer.parseInt(st.nextToken());
	int to = Integer.parseInt(st.nextToken());

	if (union(from, to)) {
		edgesCount++;
	}
}

4) 모든 가능한 간선 정보 생성

// 4. 모든 가능한 간선 정보 생성
List<Edge> edges = new ArrayList<>();
// 간선정보 저장
for (int i = 1; i <= N; i++) {
	for (int j = i + 1; j <= N; j++) {
		double weight = getDistance(spots.get(i), spots.get(j));

		// Edge 객체를 생성하여 리스트에 추가
		edges.add(new Edge(i, j, weight));
	}
}

5) 간선을 오름차순으로 정렬

// 5. 간선을 오름차순으로 정렬
Collections.sort(edges);

6) 크루스칼 알고리즘 실행

double minTotalWeight = 0; // 새로 만들어야 할 통로의 최소 길이 합
int edgesCount = 0; // 선택된 간선의 개수

for (Edge edge : edges) {
	// 사이클이 발생하지 않으면
	if (union(edge.from, edge.to)) {
		minTotalWeight += edge.w;
		edgesCount++;
	}

	if (edgesCount == N - 1)
		break;
}

7) 결과 출력

System.out.printf("%.2f\n",minTotalWeight);

⭐메서드 생성

1) getDistance()

// 거리르 구하기 위해서 제곱을 활용해야 한다.
private static double getDistance(Node n1, Node n2) {
  double dx = n1.x - n2.x;
  double dy = n1.y - n2.y;
  return Math.sqrt(dx * dx + dy * dy);
}

2) find()

private static int find(int a) {
if (parent[a] == a)
	return a;
return parent[a] = find(parent[a]);
}

3) union()

private static boolean union(int a, int b) {
int rootA = find(a);
int rootB = find(b);

// 이미 같은 집합이면 합치지 않는다.
if (rootA == rootB)
	return false;

// 작은 번호의 루트를 부모로 실행
if (rootA < rootB) {
	parent[rootB] = rootA;
} else {
	parent[rootA] = rootB;

}
return true;
}

🚀전체코드

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

//노드의 좌표를 나타내는 클래스
class Node {
	long x, y;

	public Node(long x, long y) {
		this.x = x;
		this.y = y;
	}
}

//MST 생성해야 한다.
//서로소 집합 or prim 알고리즘
class Edge implements Comparable<Edge> {
	int from, to;
	double w;

	public Edge(int from, int to, double w) {
		this.from = from;
		this.to = to;
		this.w = w;
	}

	@Override
	public int compareTo(Edge o) {
		// double 비교 시 오차 문제 때문에 Math.signum()을 사용하는 것이 안전
		return Double.compare(this.w, o.w);
	}
}

public class backjoon_1774_교감 {
	static int[] parent;

	public static void main(String[] args) throws IOException {
		System.setIn(new FileInputStream("src/input.txt"));

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(br.readLine());

		int N = Integer.parseInt(st.nextToken());
	int M = Integer.parseInt(st.nextToken());

// 1. 초기 설정
parent = new int[N + 1];
// 부모 배열 초기화
for (int i = 1; i < N + 1; i++) {
parent[i] = i;
}

// 2. 좌표값 저장
List<Node> spots = new ArrayList<>(N + 1);
spots.add(null);// 0번째는 비어두기
for (int i = 0; i < N; i++) {
	st = new StringTokenizer(br.readLine());
	long x = Long.parseLong(st.nextToken());
	long y = Long.parseLong(st.nextToken());

	spots.add(new Node(x, y));
}

// 3. 이미 연결된 M개의 통로 처리 (Union-Find로 미리 집합으로 묶기)
// 이미 연결된 간선은 부모를 같게 하기
int edgesCount = 0; // 선택된 간선의 개수
for (int i = 0; i < M; i++) {
	st = new StringTokenizer(br.readLine());
	int from = Integer.parseInt(st.nextToken());
	int to = Integer.parseInt(st.nextToken());

	if (union(from, to)) {
		edgesCount++;
	}
}

// 4. 모든 가능한 간선 정보 생성
List<Edge> edges = new ArrayList<>();
// 간선정보 저장
for (int i = 1; i <= N; i++) {
	for (int j = i + 1; j <= N; j++) {
		double weight = getDistance(spots.get(i), spots.get(j));

		// Edge 객체를 생성하여 리스트에 추가
		edges.add(new Edge(i, j, weight));
	}
}

// 5. 간선을 오름차순으로 정렬
Collections.sort(edges);

// 6. 크루스칼 알고리즘 실행

double minTotalWeight = 0; // 새로 만들어야 할 통로의 최소 길이 합


for (Edge edge : edges) {
	// 사이클이 발생하지 않으면
	if (union(edge.from, edge.to)) {
		minTotalWeight += edge.w;
		edgesCount++;
	}

	if (edgesCount == N - 1)
		break;
}

// 7. 결과 출력
System.out.printf("%.2f\n",minTotalWeight);

}

// 거리르 구하기 위해서 제곱을 활용해야 한다.
private static double getDistance(Node n1, Node n2) {
double dx = n1.x - n2.x;
double dy = n1.y - n2.y;
return Math.sqrt(dx * dx + dy * dy);
}

private static boolean union(int a, int b) {
int rootA = find(a);
int rootB = find(b);

// 이미 같은 집합이면 합치지 않는다.
if (rootA == rootB)
	return false;

// 작은 번호의 루트를 부모로 실행
if (rootA < rootB) {
	parent[rootB] = rootA;
} else {
	parent[rootA] = rootB;

}
return true;
}

private static int find(int a) {
if (parent[a] == a)
	return a;
return parent[a] = find(parent[a]);
}
}