[스터디] Java 알고리즘 2문제 (25.02.25)

1. 백준 2252 - 줄 세우기

• 위상 정렬 활용

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		int M = sc.nextInt();
		
		List<List<Integer>> graph = new ArrayList<>();
		for(int i = 0; i <= N; i++) {
			graph.add(new ArrayList<>());
		}
		
		int[] inDegree = new int[N+1];
		
		for(int i = 0; i < M; i++) {
			int a = sc.nextInt();
			int b = sc.nextInt();
			graph.get(a).add(b);
			inDegree[b]++;
		}
		
		Queue<Integer> q = new LinkedList<>();
		for(int i = 1; i <= N; i++) {
			if(inDegree[i] == 0) {
				q.offer(i);
			}
		}
		
		List<Integer> result = new ArrayList<>();
		
		while(!q.isEmpty()) {
			int current = q.poll();
			result.add(current);
			
			for(int n:graph.get(current)) {
				inDegree[n]--;
				if(inDegree[n] == 0) {
					q.offer(n);
				}
			}
		}
		
		for(int r: result) {
			System.out.print(r + " ");
		}
		
		sc.close();

	}

}

2. SWEA 1251 D4 - [S/W 문제해결 응용] 4일차 - 하나로

• MST 문제 - Prim 알고리즘 활용

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

public class Solution {

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

		int T = sc.nextInt();
		for (int t = 0; t < T; t++) {
			int N = sc.nextInt();
			int[][] arr = new int[N][2];

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

			double E = sc.nextDouble(); // 환경 부담 세율
			
			double[][] arr2 = new double[N][N];
			
			for(int i = 0; i < N; i++) {
				for(int j = 0; j < N; j++) {
					double l = euclid(arr[i], arr[j]);
					arr2[i][j] = arr2[j][i] = E * l;
				}
			}
			
			System.out.println();
			
			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] && arr2[e.t][i] != 0) {
						pq.offer(new Edge(e.t, i, arr2[e.t][i]));
					}
				}
				
			}
			sb.append("#").append(t+1).append(" ").append(Math.round(result)).append("\n");
		}
		System.out.println(sb);
		sc.close();

	}

	static double euclid(int[] p1, int[] p2) {
		return Math.pow(p2[0] - p1[0], 2) + Math.pow(p2[1] - p1[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);
		}

	}

}