[SWEA 1251] 하나로 Kruskal, Prim (JAVA)

문제 링크: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15StKqAQkCFAYD

SW Expert Academy

1. 주의할 점

- A 지점부터 B지점까지(A!=B)의 거리를 저장하는 2차배열을 생성할 필요가 없다(Long 타입으로 최대 1000*1000 생성시 메모리 손해)

- List를 이용해서 구현한다

- 소숫점 첫째자리에서 올림하는 경우는 최종단계에서만 1번 진행한다.

- 그래프 내에 간선의 수가 적다면 Kruskal이, 간선이 많다면 Prim이 적절한 알고리즘이다

 

2. 구현

[Kruskal Algorithm]

- 모든 Node를 저장하고 거리의 값이 오름차순이 되도록 정렬한다.

- 시작점과 끝점이 같은 집합이라면 연결하지 않는다 -> 연결하면 Cycle 발생

- 같은 집합이 아니라면, Node의 숫자가 작은쪽이 부모가 되도록 집합에 포함한다.

- 같은 집합인지 아닌지 확인하는 작업은 "Union-find" 알고리즘을 사용한다.

- parent 함수의 기능 : 현재 index의 조상을 찾아준다

- make_union 함수의 기능: index A와 index B를 같은 집합으로 만든다

- find 함수의 기능: index A와 index B가 같은 집합인지 확인해준다. 같은 집합일 경우 True 반환, 다른 집합일 경우 False 반환

 

[Kruskal Algorithm] - 555ms (시간복잡도: O(ElgE))

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 Solution_d4_1251_하나로_Kruskal {
	static class Info implements Comparable<Info> {
		int start, end;
		double val;

		public Info(int start, int end, double val) {
			this.start = start;
			this.end = end;
			this.val = val;
		}

		@Override
		public int compareTo(Info o) {
			return Double.compare(this.val, o.val);
		}
	}

	static int root[];
	static double x[], y[];
	static double mul;
	static List<Info> li;

	public static int parent(int idx) {
		if (root[idx] == idx)
			return idx;
		return root[idx] = parent(root[idx]);
	}

	public static void make_union(int a, int b) {
		a = parent(a);
		b = parent(b);
		if(a<b) root[b]=a;
		else root[a]=b;
	}

	public static int find(int a, int b) {
		a = parent(a);
		b = parent(b);
		if(a==b) return 1;
		else return 0;
	}
	
	public static void main(String[] args) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int test = Integer.parseInt(br.readLine());
		for (int t = 1; t <= test; t++) {
			int num = Integer.parseInt(br.readLine().trim());
			// 초기화
			x = new double[num + 1];
			y = new double[num + 1];
			li = new ArrayList<Info>();
			root = new int[num + 1];

			for (int i = 1; i <= num; i++)
				root[i] = i;

			String s = br.readLine();
			StringTokenizer st = new StringTokenizer(s);
			double vv;
			for (int i = 1; i <= num; i++) {
				vv = Double.valueOf(st.nextToken());
				x[i] = vv;
			}
			s = br.readLine();
			st = new StringTokenizer(s);
			for (int i = 1; i <= num; i++) {
				vv = Double.valueOf(st.nextToken());
				y[i] = vv;
			}
			mul = Double.parseDouble(br.readLine().trim());
			double start_x, start_y, end_x, end_y, dx, dy;
			for (int i = 1; i < num; i++) {
				start_x = x[i];
				start_y = y[i];
				for (int j = i + 1; j <= num; j++) {
					end_x = x[j];
					end_y = y[j];
					dx = (start_x - end_x) * (start_x - end_x);
					dy = (start_y - end_y) * (start_y - end_y);
					li.add(new Info(i, j, dx + dy));
				}
			}
			Collections.sort(li);
			int cnt = 0;
			long result = 0;
			while (cnt < li.size()) {
				int start = li.get(cnt).start;
				int end = li.get(cnt).end;
				int res = find(start,end);
				if (res==1) { // 사이클 형성
					cnt++;
					continue;
				}
				make_union(start,end);
				result += li.get(cnt).val;
				cnt++;
			}
			System.out.println("#" + t + " " + Math.round(mul*result));
		}
	}
}

 

[Prim Algorithm]

- 시작점을 아무곳이나 잡고 Deque에 삽입한다(여기서는 1로 잡았다)

- 현재 Node와 연결되어 있는 모든 간선을 우선순위큐에 적재하며, 우선순위 큐는 간선의 가중치가 오름차순으로 정렬되어 있다.

- 우선순위큐에서 한개씩 빼면서 다음 Index가 방문한 지점이라면 continue를, 아니라면 해당 Index를 deque에 삽입하고 위의 과정을 반복한다.

 

 

[Prim Algorithm]  - 786ms (시간복잡도: O(N^2))

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Solution_d4_1251_하나로_Prim {
	static class Info implements Comparable<Info> {
		int idx;
		double val;
		public Info(int idx, double val) {
			this.idx = idx;
			this.val = val;
		}
		@Override
		public int compareTo(Info o) {
			return Double.compare(this.val, o.val);
		}
	}

	static boolean flag[];
	static double x[], y[];
	static double mul;
	static List<Info> li[];

	public static void main(String[] args) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int test = Integer.parseInt(br.readLine());
		for (int t = 1; t <= test; t++) {
			int num = Integer.parseInt(br.readLine().trim());
			// 초기화
			flag = new boolean[num + 1];
			x = new double[num + 1];
			y = new double[num + 1];
			li = new List[num + 1];
			for(int i=1;i<=num;i++)
				li[i] = new ArrayList<>();

			String s = br.readLine();
			StringTokenizer st = new StringTokenizer(s);
			double vv;
			for (int i = 1; i <= num; i++) {
				vv = Double.valueOf(st.nextToken());
				x[i] = vv;
			}
			s = br.readLine();
			st = new StringTokenizer(s);
			for (int i = 1; i <= num; i++) {
				vv = Double.valueOf(st.nextToken());
				y[i] = vv;
			}
			mul = Double.parseDouble(br.readLine().trim());
			double start_x, start_y, end_x, end_y, dx, dy;
			for (int i = 1; i < num; i++) {
				start_x = x[i];
				start_y = y[i];
				for (int j = i + 1; j <= num; j++) {
					end_x = x[j];
					end_y = y[j];
					dx = (start_x - end_x) * (start_x - end_x);
					dy = (start_y - end_y) * (start_y - end_y);
					li[i].add(new Info(j, dx + dy));
					li[j].add(new Info(i, dx + dy));
				}
			}
			List<Info> temp;
			double result = 0;
			PriorityQueue<Info> pq = new PriorityQueue<>();
			Deque<Integer> dq = new ArrayDeque<>();
			dq.add(1);
			Info ii;
			while(!dq.isEmpty()) {
				int curNode =dq.poll();
				flag[curNode]=true;
				temp=li[curNode];
				for(int i=0;i<temp.size();i++) {
					int next = temp.get(i).idx;
					if(!flag[next]) {
						pq.add(new Info(next,temp.get(i).val));
					}
				}
				while(!pq.isEmpty()) {
					ii=pq.poll();
					if(!flag[ii.idx]) {
						flag[ii.idx]=true;
						dq.add(ii.idx);
						result+=ii.val;
						break;
					}
				}
				
			}
			System.out.println("#" + t + " " + Math.round(mul * result));
		}
	}
}