BOJ 1922 네트워크 연결

메모리 : 46208 KB (크루스칼) / 44328 KB (프림)

시간 : 512 ms / 348 ms

BOJ 1922 다리 만들기 Gold 4

풀이

1. 각 정점 -> 정점으로 가는 비용을 저장한다.
2. 비용을 기준으로 오름차순 정렬한다.
3. 비용이 정렬된 순서대로 정점을 선택해나가며, 두 정점의 부모를 확인한다.
4. 두 정점의 부모가 다르다면 연결시키고 비용을 더해준다. (부모가 같을 경우 사이클이 발생할 수 있다.)

느낀점

익숙하지 않아 기본 코드를 참고했는데 그게 다인 문제였다..
익숙해질 수 있도록 많이 연습해봐야겠다.
이전에 블로그에 짧게 정리해둔 글을 봤는데 무슨 말인지 모르겠더라..
MST도 다시 정리해봐야겠다.
그런데 최소인 값을 가진 정점들부터 순서대로 연결하는데.. 그럼.. 그리디적인 관점인 걸까?

코드 - 크루스칼 알고리즘

import java.io.*;
import java.util.*;

public class Main {
	static int N, M, cost;
	static Edge[] graph;
	static int[] parent, rank;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		M = Integer.parseInt(br.readLine());
		graph = new Edge[M];
		parent = new int[N];
		rank = new int[N];
		for (int i = 0; i < M; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken()) - 1;
			int b = Integer.parseInt(st.nextToken()) - 1;
			int cost = Integer.parseInt(st.nextToken());
			graph[i] = new Edge(a, b, cost);
		}
		
		Arrays.sort(graph);
		
		for (int i = 0; i < N; i++) {
			parent[i] = i;
		}
		
		int cnt = 0;
		for (int i = 0; i < M; i++) {
			Edge e = graph[i];
			int px = findSet(e.a);
			int py = findSet(e.b);
			
			if (px != py) {
				union(px, py);
				cost += e.cost;
				cnt++;
				if (cnt == N-1) break;
			}
		}
		
		System.out.println(cost);
	}
	
	// 부모 노드를 찾는다
	public static int findSet(int x) {
		if (parent[x] == x) {
			return x;
		} else {
			parent[x] = findSet(parent[x]);
			return parent[x];
		}
	}
	
	public static void union(int x, int y) {
		int px = findSet(x);
		int py = findSet(y);
		if (px != py) {
			link(px, py);
		}
	}
	
	public static void link(int px, int py) {
		if (rank[px] > rank[py]) {
			parent[py] = px;
		} else {
			parent[px] = py;
			if (rank[px] == rank[py])
				rank[py]++;
		}
	}
	
	static class Edge implements Comparable<Edge> {
		int a, b;
		int cost;
		public Edge(int a, int b, int cost) {
			super();
			this.a = a;
			this.b = b;
			this.cost = cost;
		}
		@Override
		public int compareTo(Edge o) {
			return this.cost - o.cost;
		}
	}
}

코드 - 프림 알고리즘

import java.io.*;
import java.util.*;

public class Main {
	static int N, M, cost;
	static int[] parent, costs;
	static int[][] graph;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		M = Integer.parseInt(br.readLine());
		graph = new int[N][N];
		for (int i = 0; i < M; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken()) - 1;
			int b = Integer.parseInt(st.nextToken()) - 1;
			int cost = Integer.parseInt(st.nextToken());
			graph[a][b] = graph[b][a] = cost;
		}
		parent = new int[N];
		costs = new int[N];
		
		int r = 0;
		for (int i = 0; i < graph[r].length; i++) {
			if(graph[r][i] > 0) {
				parent[i] = r;
				costs[i] = graph[r][i];
			} else {
				parent[i] = -1;
				costs[i] = Integer.MAX_VALUE;
			}
		}
		
		parent[r] = r;
		costs[r] = 0;
		boolean[] selected = new boolean[N];
		selected[r] = true;
		
		for (int i = 1; i < N; i++) {
			int minIndex = -1;
			int min = Integer.MAX_VALUE;
			for (int j = 0; j < costs.length; j++) {
				if(!selected[j] && min > costs[j]) {
					min = costs[j];
					minIndex = j;
				}
			}
			r = minIndex;
			selected[r] = true;
			
			for (int j = 0; j < graph[r].length; j++) {
				if(!selected[j] && graph[r][j] != 0 && costs[j] > graph[r][j]) {
					costs[j] = graph[r][j];
					parent[j] = r;
				}
			}
			
		}
		for (int i = 0; i < costs.length; i++) {
			cost += costs[i];
		}
		
		System.out.println(cost);
	}
}