[스터디] MST 2문제 출제 및 풀기 + 도전 문제 2문제 (25.02.24)

MST 문제 출제

1. 우주 정거장 건설 문제

우주 탐사선들이 정거장을 세우기 위해 N개의 행성에 기지를 건설하려 한다.

각 행성은 (x, y) 좌표를 가지며, 두 행성을 연결하는 비용은 유클리드 거리로 정의된다.

모든 행성을 최소 비용으로 연결하는 프로그램을 작성하시오.

📍 입력 형식

N (행성 개수)
N개의 줄: x y (각 행성의 좌표)

📍 출력 형식

최소 신장 트리의 총 비용을 출력하시오.

예제 입력

4
1 1
2 2
2 4
5 6

예제 출력

7.02 (소수점 2번째 자리까지 출력)

➡️ Kruskal 알고리즘 풀이

package algo_250224;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class 우주정거장건설_Kruskal {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt();
		int[][] stations = new int[N][2];
		for (int i = 0; i < N; i++) {
			stations[i][0] = sc.nextInt();
			stations[i][1] = sc.nextInt();
		}

		List<Edge> edges = new ArrayList<>();

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				double dist = calEuclideanDistance(stations[i], stations[j]);
				edges.add(new Edge(i, j, dist));
			}
		}

		Collections.sort(edges);

		makeSet(N);

		double result = 0;
		int pickCnt = 0;

		for (Edge e : edges) {
			if (union(e.f, e.t)) {
				result += e.w;
				if (++pickCnt == (N - 1)) break;
			}
		}

		System.out.printf("%.2f\n", result);
		sc.close();

	}

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

	static int[] p;

	static void makeSet(int n) {
		p = new int[n];
		for (int i = 0; i < n; i++) {
			p[i] = i;
		}
	}

	static int find(int e) {
		if (e != p[e]) {
			p[e] = find(p[e]);
		}
		return p[e];
	}

	static boolean union(int f, int t) {
		int fp = find(f);
		int tp = find(t);

		if (fp == tp)
			return false;

		p[tp] = fp;
		return true;
	}

	static class Edge implements Comparable<Edge> {
		int f, t;
		double w;

		public Edge(int f, int t, double w) {
			super();
			this.f = f;
			this.t = t;
			this.w = w;
		}

		@Override
		public int compareTo(Edge o) {
			return Double.compare(w, o.w);
		}

	}

}

➡️ Prim 알고리즘 풀이

package algo_250224;

import java.util.PriorityQueue;
import java.util.Scanner;

public class 우주정거장건설_Prim {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt();
		int[][] stations = new int[N][2];
		for (int i = 0; i < N; i++) {
			stations[i][0] = sc.nextInt();
			stations[i][1] = sc.nextInt();
		}

		double[][] arr = new double[N][N];

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				double dist = calEuclideanDistance(stations[i], stations[j]);
				arr[i][j] = arr[j][i] = dist;
			}
		}

		boolean[] visited = new boolean[N];
		double result = 0;
		int pickCnt = 0;

		PriorityQueue<Edge> pq = new PriorityQueue<>();
		pq.offer(new Edge(0, 0, 0));

		while (!pq.isEmpty()) {
			Edge e = pq.poll();

			if (visited[e.t]) continue;
			visited[e.t] = true;
			result += e.w;

			if (++pickCnt == N) break;

			for (int i = 0; i < N; i++) {
				if (!visited[i] && arr[e.t][i] != 0) {
					pq.offer(new Edge(e.t, i, arr[e.t][i]));
				}
			}
		}

		System.out.printf("%.2f\n", result);
		sc.close();

	}

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

	static class Edge implements Comparable<Edge> {
		int f, t;
		double w;

		public Edge(int f, int t, double w) {
			super();
			this.f = f;
			this.t = t;
			this.w = w;
		}

		@Override
		public int compareTo(Edge o) {
			return Double.compare(w, o.w);
		}

	}

}

2. 글로벌 해저 케이블 네트워크 구축 문제

한 글로벌 통신 회사가 N개의 대륙(정점)을 연결하는 M개의 해저 광케이블(간선) 후보를 조사했다.

각 해저 케이블은 특정 두 대륙을 연결하며, 설치 비용이 다르다.

모든 대륙 간 데이터 전송이 가능하도록 최소 비용으로 광케이블을 설치해야 한다.

📍 입력 형식

N M
A B C // A 대륙과 B 대륙을 연결하는 해저 케이블의 설치 비용 C
(1 ≤ N ≤ 100, 1 ≤ M ≤ 1,000, 1 ≤ C ≤ 100,000)

📍 출력 형식

모든 대륙을 연결하는 최소 비용을 출력

예제 입력

5 6
1 2 75000
1 3 88000
2 3 92000
2 4 110000
3 5 103000
4 5 120000

예제 출력

376000

➡️ Kruskal 알고리즘 풀이

package algo_250224;

import java.util.Arrays;
import java.util.Scanner;

public class 글로벌해저케이블네트워크구축_Kruskal {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt();
		int M = sc.nextInt();

		Edge[] edges = new Edge[M];

		for (int i = 0; i < M; i++) {
			int f = sc.nextInt();
			int t = sc.nextInt();
			int w = sc.nextInt();

			edges[i] = new Edge(f, t, w);

		}

		Arrays.sort(edges);

		makeSet(N + 1); // 정점 번호가 1부터 시작하기 때문

		int result = 0;
		int pickCnt = 0;

		for (Edge e : edges) {
			if (union(e.f, e.t)) {
				result += e.w;
				if (++pickCnt == (N - 1)) break;
			}
		}

		System.out.println(result);
		sc.close();

	}

	static int[] p;

	static void makeSet(int n) {
		p = new int[n];
		for (int i = 0; i < n; i++) {
			p[i] = i;
		}
	}

	static int find(int e) {
		if (e != p[e]) {
			p[e] = find(p[e]);
		}
		return p[e];
	}

	static boolean union(int f, int t) {
		int fp = find(f);
		int tp = find(t);

		if (fp == tp)
			return false;

		p[tp] = fp;
		return true;
	}

	static class Edge implements Comparable<Edge> {
		int f, t, w;

		public Edge(int f, int t, int w) {
			super();
			this.f = f;
			this.t = t;
			this.w = w;
		}

		@Override
		public int compareTo(Edge o) {
			return Integer.compare(w, o.w);
		}

	}

}

➡️ Prim 알고리즘 풀이

package algo_250224;

import java.util.PriorityQueue;
import java.util.Scanner;

public class 글로벌해저케이블네트워크구축_Prim {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt();
		int M = sc.nextInt();

		int[][] arr = new int[N + 1][N + 1];

		for (int i = 0; i < M; i++) {
			int f = sc.nextInt();
			int t = sc.nextInt();
			int w = sc.nextInt();

			arr[f][t] = arr[t][f] = w;

		}

		boolean[] visited = new boolean[N + 1];
		int result = 0;
		int pickCnt = 0;

		PriorityQueue<Edge> pq = new PriorityQueue<>();
		pq.offer(new Edge(1, 1, 0));

		while (!pq.isEmpty()) {
			Edge e = pq.poll();

			if (visited[e.t]) continue;
			visited[e.t] = true;
			result += e.w;

			if (++pickCnt == N) break;

			for (int i = 1; i <= N; i++) {
				if (!visited[i] && arr[e.t][i] != 0) {
					pq.offer(new Edge(e.t, i, arr[e.t][i]));
				}
			}
		}

		System.out.println(result);
		sc.close();

	}

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

	static class Edge implements Comparable<Edge> {
		int f, t, w;

		public Edge(int f, int t, int w) {
			super();
			this.f = f;
			this.t = t;
			this.w = w;
		}

		@Override
		public int compareTo(Edge o) {
			return Integer.compare(w, o.w);
		}

	}

}

👩🏻‍💻 도전 문제 풀기

1. SWEA 1208 D3 - [S/W 문제해결 기본] 1일차 - Flatten

import java.util.Arrays;
import java.util.Scanner;

public class Solution {
	public static void main(String[] args) {

		StringBuilder sb = new StringBuilder();
		Scanner sc = new Scanner(System.in);
		int T = 10;

		for (int i = 0; i < T; i++) {
			sb.append("#").append(i + 1).append(" ");

			int dump = sc.nextInt();
			int[] arr = new int[100];

			for (int j = 0; j < 100; j++) {
				arr[j] = sc.nextInt();
			}

			for (int j = 0; j < dump; j++) {
				Arrays.sort(arr); // 정렬

				if (arr[99] <= 1) break; // 최대값이 1보다 작거나 같아지면 멈춤

				arr[99] -= 1; // 가장 큰 값에 +1
				arr[0] += 1; // 가장 작은 값에 -1
			}

			Arrays.sort(arr); // 다시 한번 더 정렬
			sb.append(arr[99] - arr[0]).append("\n");
		}

		System.out.println(sb);

	}

}

2. SWEA 2001 D2 - 파리 퇴치

import java.util.Scanner;

public class Solution {

	public static void main(String[] args) {
		StringBuilder sb = new StringBuilder();
		Scanner sc = new Scanner(System.in);

		int T = sc.nextInt();
		for (int t = 0; t < T; t++) {
			sb.append("#").append(t + 1).append(" ");

			int N = sc.nextInt();
			int M = sc.nextInt();

			int[][] arr = new int[N][N];

			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					arr[i][j] = sc.nextInt();
				}
			}

			int maxSum = 0; // 최대 파리 수를 저장

			for (int i = 0; i <= N - M; i++) { // 세로 방향으로 이동
				for (int j = 0; j <= N - M; j++) { // 가로 방향으로 이동
					int sum = 0;
					for (int x = 0; x < M; x++) {
						for (int y = 0; y < M; y++) {
							sum += arr[i + x][j + y];
						}
					}
					if (sum > maxSum) {
						maxSum = sum;
					}
				}
			}

			sb.append(maxSum).append("\n");
		}
		System.out.println(sb);
		sc.close();

	}

}

728x90

'LG 유플러스 유레카 SW > 스터디' 카테고리의 다른 글

[스터디] Java 알고리즘 2문제 (25.02.25) (0)	2025.02.25
[스터디] Java 알고리즘 2문제 (25.02.21) (1)	2025.02.21
[스터디] Java 도전 문제 3문제 (25.02.20) (0)	2025.02.20
[스터디] Java 프로그래머스 PCCE 기출 14문제 (25.02.19) (1)	2025.02.19
[스터디] Java 프로그래머스 기초 24문제 & 머쓱이 획득 (25.02.18) (1)	2025.02.18

MST 문제 출제

1. 우주 정거장 건설 문제

📍 입력 형식

📍 출력 형식

예제 입력

예제 출력

2. 글로벌 해저 케이블 네트워크 구축 문제

📍 입력 형식

📍 출력 형식

예제 입력

예제 출력

👩🏻‍💻 도전 문제 풀기

1. SWEA 1208 D3 - [S/W 문제해결 기본] 1일차 - Flatten

2. SWEA 2001 D2 - 파리 퇴치

'LG 유플러스 유레카 SW > 스터디' 카테고리의 다른 글

티스토리툴바