java 알고리즘 스터디 10주차 - MST (Kruskal, Prim)

16398 행성 연결

📌문제 링크

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

💡 문제 풀이

행성(정점)의 수가 최대 1000개인데, 간선의 수는 N*N만큼 들어와 정점의 수가 더 작으므로 프림 알고리즘을 활용해 풀었다.

📋코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	private static class Edge implements Comparable<Edge>{
		int to;	// 연결된 행성 번호
		long cost;	// 플로우 관리 비용

		public Edge(int to, long cost) {
			super();
			this.to = to;
			this.cost = cost;
		}

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

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stk;
		
        // 입력
		int N = Integer.parseInt(br.readLine());
		ArrayList<Edge>[] adj = new ArrayList[N];
		for (int i = 0; i < N; i++) {
			adj[i] = new ArrayList<>();
		}
		
		boolean[] visited = new boolean[N];
		
		long cost;
		for (int i = 0; i < N; i++) {
			stk = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				cost = Long.parseLong(stk.nextToken());
				if (i == j) continue;
				
				adj[i].add(new Edge(j, cost));
			}
		}
		
        // 비용이 적은 간선을 찾기 위해 우선순위 큐 사용
		PriorityQueue<Edge> queue = new PriorityQueue<>();
		int cnt = 1;
		long result = 0;
		
        // 임의의 정점 (0번) 행성부터 방문
		queue.addAll(adj[0]);
		visited[0] = true;
		
        // 이미 방문한 0번을 제외한 N-1개의 행성을 연결할 때까지 반복
		while(cnt != N) {
			Edge min = queue.poll(); // 가장 가중치가 적은 간선
			
			if(visited[min.to]) continue; // 이미 방문한 정점이면 건너뜀
			
			result += min.cost; // 비용 합산
			queue.addAll(adj[min.to]); // 연결된 간선 추가
			visited[min.to] = true;
			cnt++;
		}
		
		System.out.println(result);
	}

}

⏱ 시간 복잡도

메모리 : 149352KB, 시간 : 1240ms

1922 네트워크 연결

📌문제 링크

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

💡 문제 풀이

위 문제와 동일하게 프림 알고리즘으로 풀었다.
(정점의 수 최대 1000개, 간선의 수가 최대 100,000개)

📋코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	private static class Edge implements Comparable<Edge> {
		int to, cost;

		public Edge(int to, int cost) {
			super();
			this.to = to;
			this.cost = cost;
		}

		@Override
		public int compareTo(Edge o) {
			return Integer.compare(cost, o.cost);
		}
		
	}
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stk;
		
		int N = Integer.parseInt(br.readLine());
		int M = Integer.parseInt(br.readLine());
		
		ArrayList<Edge>[] adj = new ArrayList[N+1];
		for (int i = 1; i < N+1; i++) {
			adj[i] = new ArrayList<>();
		}
		
		int from , to, cost;
		for (int i = 0; i < M; i++) {
			stk = new StringTokenizer(br.readLine());
			from = Integer.parseInt(stk.nextToken());
			to = Integer.parseInt(stk.nextToken());
			cost = Integer.parseInt(stk.nextToken());
			
			adj[from].add(new Edge(to, cost));
			adj[to].add(new Edge(from, cost));
		}
		
		PriorityQueue<Edge> queue = new PriorityQueue<>();
		queue.addAll(adj[1]);
		boolean[] visited = new boolean[N+1];
		visited[1] = true;
		
		int cnt = 1;
		int result = 0;
		
		Edge min;
		while(cnt != N) {
			min = queue.poll();
			
			if (visited[min.to]) continue;
			
			result += min.cost;
			visited[min.to] = true;
			queue.addAll(adj[min.to]);
			cnt++;
		}
		
		System.out.println(result);
	}

}

⏱ 시간 복잡도

메모리 : 52656KB, 시간 : 496ms

1368 물대기

📌문제 링크

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

💡 문제 풀이

정점의 수가 최대 300개, 간선의 수가 N*N개 입력받으므로 프림 알고리즘을 활용해 풀었다.

이 문제가 다른 문제와 다른 점은 자기 자신을 연결할 때 비용이 들고, 모든 정점을 연결하지 않고 자기 자신을 방문해도 된다는 점이다.

처음 i번째 논에 우물을 팔 때 드는 비용을 모두 PriorityQueue에 넣는 코드를 추가해 해결했다.

📋코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	private static class Edge implements Comparable<Edge> {
		int to, cost;

		public Edge(int to, int cost) {
			super();
			this.to = to;
			this.cost = cost;
		}

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

	}
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stk;
		
		int N = Integer.parseInt(br.readLine());
		
        // i번째 논에 우물을 팔 때 드는 비용 우선순위 큐에 추가
		PriorityQueue<Edge> pq = new PriorityQueue<>();
		for (int i = 0; i < N; i++) {
			pq.add(new Edge(i, Integer.parseInt(br.readLine())));
		}
		
        
        // i번째 논과 j번째 논을 연결하는 데 드는 비용 인접리스트 생성
		ArrayList<Edge>[] adj = new ArrayList[N];
		
		for (int i = 0; i < N; i++) {
			adj[i] = new ArrayList<>();
		}
		
		int cost = 0;
		for (int i = 0; i < N; i++) {
			stk = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				cost = Integer.parseInt(stk.nextToken());
				if (i==j) continue;	// 자기 자신은 인접리스트에 추가하지 않음
				adj[i].add(new Edge(j, cost));
			}
		}
		
		
        // 임의의 정점을 방문하지 않고 우선순위 큐에서 비용이 최소인 간선을 얻음
		boolean[] visited = new boolean[N];
		int result = 0;
		int cnt = 0;
		
		while(cnt < N) {
			Edge min = pq.poll();
			
			if (visited[min.to]) continue;
			
			result += min.cost;
			pq.addAll(adj[min.to]);
			visited[min.to] = true;
			cnt++;
		}
		
		System.out.println(result);
		
	}

}

⏱ 시간 복잡도

메모리 : 27760KB, 시간 : 340ms

1774 우주신과의 교감

📌문제 링크

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

💡 문제 풀이

이 문제는 우주신의 개수의 최댓값(1000)과 이미 연결된 신들과의 통로의 개수 최댓값(1000)이 같으므로 크루스칼 알고리즘으로 풀어보았다.

여기서 주의할 점은 연결하는 비용을 직접 입력받는 것이 아니라 2차원 좌표를 입력받는다는 것이다.

좌표 사이 거리를 구하는 함수를 만들어 인접리스트에 가중치를 포함한 간선을 추가한 뒤, 가중치가 작은 순서대로 인접리스트를 정렬하고 union-find 알고리즘으로 정점을 연결했다.

📋코드

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

public class Main {
	// 좌표를 입력받기 위한 class
	private static class Pos {
		int x, y;

		public Pos(int x, int y) {
			super();
			this.x = x;
			this.y = y;
		}
		
	}
	
    // 간선 class
	private static class Edge implements Comparable<Edge> {
		int from, to;
		double cost;

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

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

	}
	
	static int[] parents;	// union-find 알고리즘을 위한 배열
	static Pos[] godList;	// 신들의 정점을 저장할 배열
	static int N, M;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stk = new StringTokenizer(br.readLine());
		N = Integer.parseInt(stk.nextToken());
		M = Integer.parseInt(stk.nextToken());
		
        // parents 배열 초기화
		parents = new int[N];
		
		for (int i = 0; i < N; i++) {
			makeSet(i);
		}
		
        // 신들의 좌표 입력
		godList = new Pos[N];
		
		for (int i = 0; i < N; i++) {
			stk = new StringTokenizer(br.readLine());
			godList[i] = new Pos(Integer.parseInt(stk.nextToken()), Integer.parseInt(stk.nextToken()));
		}
		
        // 인접리스트에 신들 사이의 거리를 구해 간선 추가
		List<Edge> adjList = new ArrayList<Edge>();
		for (int i = 0; i < N; i++) {
			for (int j = i; j < N; j++) {
				if (i==j) continue;
				adjList.add(new Edge(i, j, getDist(i, j)));
			}
		}
		
        // 이미 연결된 신들을 union 함수로 합침
		for (int i = 0; i < M; i++) {
			stk = new StringTokenizer(br.readLine());
			union(Integer.parseInt(stk.nextToken()) - 1, Integer.parseInt(stk.nextToken()) - 1);
		}
		
		double result = 0;
		Collections.sort(adjList); // 인접리스트 정렬
		
        // 가중치가 적은
		for (Edge edge : adjList) {
        	// 연결된 신이 아니라면 연결
			if (union(edge.to, edge.from)) {
            	// 가중치 더함
				result += edge.cost;
                // 모든 신이 연결됐다면 반복 멈춤
				if (checkConnection()) break;
			}
		}
		
		System.out.printf("%.2f\n", result);
		
	}
	
    // 모든 신이 연결됐는지 확인하는 함수
	private static boolean checkConnection() {
		int cnt = 0;
		for (int i = 0; i < N; i++) {
        	// parents 함수의 root가 몇 개인지 count
			if (parents[i] == i) cnt++;
		}
		
        // root가 두 개 이상이면 모두 연결되지 않음
		if (cnt > 1) return false;
		else return true;
	}
	
    // 좌표 사이의 거리를 구하는 함수
	private static double getDist(int i, int j) {
		return Math.sqrt(Math.pow(godList[i].x - godList[j].x, 2) + Math.pow(godList[i].y - godList[j].y, 2));
	}
	
    
	private static boolean union(int v, int u) {
		int root1 = findSet(v);
		int root2 = findSet(u);
		
		if (root1 == root2) return false;
		
		parents[root1] = root2;
		return true;
	}

	private static int findSet(int v) {
		if (parents[v] == v) return v;
		return parents[v] = findSet(parents[v]);
	}

	private static void makeSet(int v) {
		parents[v] = v;
	}

}

⏱ 시간 복잡도

메모리 : 44388KB, 시간 : 672ms