b1774. 우주신과의 교감

 

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

 

 

 

🌌 자바로 푸는 우주신과의 교감 문제 풀이

 

---

 

📌 문제 개요

 

백준 1774번 우주신과의 교감 문제는

N개의 신들과 이미 연결된 M개의 통로 정보가 주어졌을 때,

모든 우주신이 연결되도록 추가로 연결해야 할 최소 거리의 합을 구하는 문제입니다.

 

• 각 우주신은 2차원 좌표 위에 존재
• 이미 연결된 통로는 추가 비용 없이 사용 가능
• 목표는 전체 우주신을 연결하는 최소 비용

 

---

 

💡 예제 입력

4 1
1 1
2 2
2 4
3 3
1 4

 

예제 출력

2.00

 

---

 

🛠 알고리즘 접근 방식

 

이 문제는 기존 연결 정보를 고려한 최소 신장 트리(MST) 문제입니다.

 

 

✅ 핵심 아이디어

 

• 크루스칼 알고리즘을 사용해 거리 기준 오름차순 간선 선택
• M개의 이미 연결된 통로는 먼저 union() 처리
• 이후 모든 가능한 두 점 간 거리(간선)를 구해 PriorityQueue에 저장
• 사이클을 피하며 최소 간선을 선택하여 MST 완성

 

---

 

🧾 코드 해설

 

 

🪐 좌표 입력 및 유니온 초기화

N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
gods = new int[N+1][2];
p = new int[N+1];
for(int i = 1; i <= N; i++) {
    st = new StringTokenizer(br.readLine());
    gods[i][0] = Integer.parseInt(st.nextToken());
    gods[i][1] = Integer.parseInt(st.nextToken());
    p[i] = i;
}

 

🛰 이미 연결된 통로 union 처리

for(int i = 1; i <= M; i++) {
    st = new StringTokenizer(br.readLine());
    int a = Integer.parseInt(st.nextToken());
    int b = Integer.parseInt(st.nextToken());
    if(union(a,b)) count++;
}

 

🌐 가능한 간선 생성 (모든 두 점 쌍)

for(int i = 1; i <= N; i++) {
    for (int j = i + 1; j <= N; j++) {
        pq.add(new Line(i,j));
    }
}

 

🌠 크루스칼 알고리즘으로 MST 완성

while (!pq.isEmpty()) {
    if (count == N - 1) break;

    Line l = pq.poll();
    if (union(l.a, l.b)) {
        answer += l.value;
        count++;
    }
}
System.out.println(String.format("%.2f", answer));

 

📐 거리 계산 함수

private static double getDistance(int a, int b) {
    return Math.sqrt(Math.pow(gods[a][0]-gods[b][0],2) + Math.pow(gods[a][1]-gods[b][1],2));
}

 

---

 

✅ 핵심 포인트 요약

 

• 크루스칼을 사용한 MST 문제
• 기존 간선(M개)은 미리 union() 처리해서 연결 상태 반영
• 거리 계산은 유클리드 거리 (sqrt(x² + y²))
• 최소 간선 수는 N - 1이며, count로 추적

 

---

 

🚀 결론: 연결을 확장하는 최소한의 길

 

이 문제는 MST에서 기존 연결 정보가 주어질 때의 처리 방식을 묻는 문제입니다.

사이클을 피하면서, 가능한 한 짧은 거리의 통로만을 선택해야 하죠.