1774번 - 우주신과의 교감
2024-05-15
5분 분량
JAVA백준
문제 풀이 시간 : 3시간
문제 요약
- 황선자씨는 N-1명의 우주신과 교감을 할 수 있다.
- 황선자씨나 우주신들이 연결된 통로 M개가 존재한다.
- 아직 연결되지 않은 우주신들이 연결되기 위해 필요한 통로의 최소 길이를 구하라
문제 풀이
문제를 읽다가 재밌어 보여서 풀기 시작했는데
풀다 보니 얼마 전에 알고리즘 수업 시간에 배웠던 최소 신장 트리(MST) 문제라는 것을 깨달았다.
그래서 Prim의 알고리즘으로 풀려고 시도를 했는데….
초기 코드
java
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class Main {
public static class Pair {
private int x, y;
Pair(int x, int y) {
this.x = x;
this.y = y;
}
}
public static int N;
public static int M;
public static ArrayList<Pair> gods;
public static ArrayList<Integer> road;
public static double value[][];
public static double result;
public static void find() { //프림의 알고리즘
if (road.size() == N)
return;
double min = Double.MAX_VALUE;
int min_idx = -1;
for (int i = 0; i < road.size(); i++) { //현재 연결된 우주신들과 연결되지 않은 우주신 사이에 가장 짧은 통로 찾기
for (int j = 0; j < N; j++) {
if(j==road.get(i))
continue;
if(road.contains(j))
continue;
if(value[road.get(i)][j]<min){
min = value[road.get(i)][j];
min_idx = j;
}
}
}
road.add(min_idx); //새로 연결된 우주신 넣기
result += min; //최소 길이 추가
find(); //재귀
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
gods = new ArrayList<>();
road = new ArrayList<>();
int x, y;
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
x = Integer.parseInt(st.nextToken());
y = Integer.parseInt(st.nextToken());
gods.add(new Pair(x, y));
}
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
road.add(Integer.parseInt(st.nextToken())-1);
road.add(Integer.parseInt(st.nextToken())-1);
}
value = new double[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
value[i][j] = Math.sqrt(Math.pow((gods.get(i).x - gods.get(j).x), 2) + Math.pow((gods.get(i).y - gods.get(j).y), 2));
}
}
result = 0;
find();
System.out.println(result);
}
}얼레?
예상은 했지만 바로 시간 초과가 나왔다.
확실히 조행래 교수님이 알려주신 방법대로 안 해서 그런가?
하고 배운 대로 풀어보려고 코드를 다시 짜봤다.
중기 코드
java
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class Main {
public static class Pair {
private int x, y;
Pair(int x, int y) {
this.x = x;
this.y = y;
}
}
public static int N;
public static int M;
public static ArrayList<Pair> gods;
public static ArrayList<Integer> road;
public static int nearest[];
public static double value[][];
public static double result;
public static void find() {
if (road.size() == N)
return;
double min = Double.MAX_VALUE;
int min_idx = -1;
for(int i=0;i<N;i++){
if(road.contains(i)) //연결된 우주신은 패스
continue;
if(value[i][nearest[i]]<min){ //최소 길이 찾기
min = value[i][nearest[i]];
min_idx = i;
}
}
result+=Math.sqrt(min);
road.add(min_idx);//새로 찾은 우주신 넣기
resetNearest();//nearest 다시 초기화
find();
}
public static void resetNearest(){ //nearest배열 초기화 함수
for(int i=0;i<N;i++) {
if (road.contains(i))
continue;
int near = -1;
double near_num = Double.MAX_VALUE;
for (int j = 0; j < N; j++) { //연결된 우주신들 중 j우주신과 가장 가까운 우주신 찾기
if (i == j)
continue;
if (road.contains(j)) {
if (value[i][j] < near_num) {
near_num = value[i][j];
near = j;
}
}
}
nearest[i] = near;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
gods = new ArrayList<>();
road = new ArrayList<>();
nearest = new int[N];
int x, y;
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
x = Integer.parseInt(st.nextToken());
y = Integer.parseInt(st.nextToken());
gods.add(new Pair(x, y));
}
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
road.add(Integer.parseInt(st.nextToken())-1);
road.add(Integer.parseInt(st.nextToken())-1);
}
value = new double[N][N];
for (int i = 0; i < N; i++) {
for (int j = i+1; j < N; j++) {
value[i][j] = Math.pow((gods.get(i).x - gods.get(j).x), 2) + Math.pow((gods.get(i).y - gods.get(j).y), 2);
value[j][i] = value[i][j];
}
}
resetNearest(); //nearest 배열 초기화
result = 0;
find();
System.out.println(result);
}
}이렇게 해도 똑같이 시간 초과가 나버려서
결국 다른 사람의 풀이를 참조할 수 밖에 없었다..
최종 코드
java
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class Main {
//우선순위 큐에서 사용하기 위한 클래스
static class Path implements Comparable<Path> {
int vertex;
double weight;
Path(int vertex, double weight) {
this.vertex = vertex;
this.weight = weight;
}
@Override
public int compareTo(Path other) {
return Double.compare(this.weight, other.weight);
}
}
//엣지 클래스
static class Edge {
int from, to;
double weight;
Edge(int from, int to, double weight) {
this.from = from;
this.to = to;
this.weight = weight;
}
}
//프림 알고리즘
public static double find(List<List<Edge>> edges, int N) {
boolean[] connected = new boolean[N]; //현재 연결된 우주신들
double[] minWeight = new double[N]; //각 우주신들의 최소 거리
//시작 노드를 제외하고 모든 노드 가중치 무한대
for (int i = 1; i < N; i++) {
minWeight[i] = Double.MAX_VALUE;
}
PriorityQueue<Path> pq = new PriorityQueue<>();
pq.add(new Path(0, 0));
double result = 0;
while (!pq.isEmpty()) {
Path path = pq.poll();
int god = path.vertex;
double weight = path.weight;
//이미 연결된 우주신이면 패스
if (connected[god]) continue;
//현재 우주신을 연결시킴
connected[god] = true;
//현재 우주신의 최소 거리를 결과에 추가
result += weight;
//현재 우주신과 다른 우주신들 사이 거리 검사
for (Edge edge : edges.get(god)) {
//연결되지 않은 우주신들의 최소 거리 업데이트
if (!connected[edge.to] && minWeight[edge.to] > edge.weight) {
minWeight[edge.to] = edge.weight;
pq.add(new Path(edge.to, edge.weight));
}
}
}
return result;
}
public static void main(String[] args) throws IOException {
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());
long[][] coordinates = new long[N][2];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
coordinates[i][0] = Long.parseLong(st.nextToken());
coordinates[i][1] = Long.parseLong(st.nextToken());
}
List<List<Edge>> edges = new LinkedList<>();
for (int i = 0; i < N; i++) {
edges.add(new LinkedList<>());
}
//이미 연결된 우주신들 사이의 거리 0으로 설정
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int from = Integer.parseInt(st.nextToken()) - 1;
int to = Integer.parseInt(st.nextToken()) - 1;
edges.get(from).add(new Edge(from, to, 0));
edges.get(to).add(new Edge(to, from, 0));
}
//모든 우주신들 사이 거리 계산, 추가
for (int i = 0; i < N - 1; i++) {
for (int j = i + 1; j < N; j++) {
double weight = Math.sqrt(Math.pow(coordinates[j][0] - coordinates[i][0], 2) +
Math.pow(coordinates[j][1] - coordinates[i][1], 2));
edges.get(i).add(new Edge(i, j, weight));
edges.get(j).add(new Edge(j, i, weight));
}
}
System.out.printf("%.2f", find(edges, N));
}
}
교수님 말대로 생각으로 하는 거랑 구현은 하늘과 땅 차이인 것 같다.
구현을 많이 해보자…
함께 읽으면 좋은 글
코딩 테스트2026-04-02
5430번 - AC
함수 R은 배열을 뒤집는 연산 함수 D는 첫 번째 원소를 버리는 연산 단, 배열이 비어 있을 때 D를 수행하면 error 주어진 함수 문자열을 순서대로 수행한 뒤 최종 배열을 출력하는 문제 처음에는 문제 설명 그대로 R이 나올 때마다 배열을 실제로 뒤집고, D가 나오면 맨 앞…
코딩 테스트2026-04-02
1966번 - 프린터 큐
여러 문서가 큐에 들어 있고, 각 문서마다 중요도가 있음 맨 앞 문서를 확인했을 때, 더 높은 중요도의 문서가 뒤에 하나라도 있으면 맨 뒤로 보냄 그렇지 않으면 바로 인쇄 특정 위치의 문서가 몇 번째로 인쇄되는지 구하는 문제 이 문제는 프린터의 동작을 그대로 구현하면 되는…
코딩 테스트2026-03-29
1158 - 요세푸스 문제
1번부터 N번까지 사람이 원형으로 앉아 있음 순서대로 K번째 사람을 제거 모든 사람이 제거될 때까지 반복 제거되는 순서를 출력하는 문제 이 문제는 원형으로 순회하면서 K번째를 제거하는 과정을 그대로 구현하면 된다.
코딩 테스트2026-03-29
2164번 - 카드2
1부터 N까지 카드가 순서대로 쌓여 있음 맨 위 카드를 버리고, 그다음 맨 위 카드를 맨 아래로 옮기는 과정을 반복 마지막에 남는 카드 번호를 구하는 문제 이 문제는 규칙을 찾기보다, 문제에서 하라는 과정을 그대로 구현하면 된다. 카드 더미에서 반복되는 동작은 두 가지다.