[JAVA] [SWEA] 1251. 하나로 ( union & find 설명까지 )

본 프로젝트에서는 인도네시아 내의 모든 섬을 해저터널로 연결하는 것을 목표로 합니다.

해저터널은 반드시 두 섬을 선분으로 연결하며, 두 해저 터널이 교차된다 하더라도 물리적으로는 연결되지 않는 것으로 가정합니다.

 

이 문제의 경우... 참 애먹인 문제입니다.

 

처음 접했을때는 어떻게 풀지 몰랐다가

 

나중가서는 아 그냥 완탐하면 되겠네 했다가....

 

그 다음에는 문제 자체를 이해 못하여서 다익스트라로 다 방문도 해봤다가...

 

최근에 다시 그래프 문제를 공부하면서 크루스칼과 Union Find 알고리즘을 공부하기 시작하면서 문제가 이해되기 시작하고 해결할 수 있게 되었다.

 

Union Find의 개념을 다른 글에 포스팅 하기 보다 여기에 몰아서 한번에 적도록 하겠다.

 

나는 다른 블로그들을 많이 보면서 이해하였지만 사실상 핵심은

 

============================================================================

1. 무리를 만들어 준다.1-1 무리의 대표를 만들어준다. 보통 다른 블로그들을 보면 숫자가 작은 것들을 대표로 만들어주거나 한다.

 

2. 무리와 무리 혹은 한 노드와 한 노드 마지막으로 한 노드와 무리가 합쳐질 경우 1-1과 똑같이 숫자가 작은 숫자가 대표가 된다.

2-1 쉽게 생각하면 1, 2, 3의 대표는 1이라고 가정 그 상황에서 4가 들어온다면 4는 1의 밑으로 들어가게 된다.

2-2 1, 2, 3 과 4, 5, 6이 합쳐지게 된다면 1, 2, 3의 대표는 1이고 4, 5, 6의 대표는 4인데 더 작은 숫자가 1이므로 4는 1밑으로 들어가게 됩니다.

============================================================================

굳이 트리로 표현하지 않고 글로 보여주냐면 저는 개인적으로 그림을 통해서 그리는 것 보다

 

저렇게 글로 이때는 이렇게 한다 저때는 저렇게 한다. 라는게 if문으로 작성하기가 더 쉬웠고

 

이 노드는 어쩌고 저 노드는 어쩌고 보다는 구체적으로 다른 말을 써서 하는게 더 이해하기 쉬웠기 때문이다.

 

자 다시 본문으로 돌아와서

 

Union Find를 하기 위해선 먼저 해야 할 것은 root 혹은 parent 설정이다.무슨 말인가 싶을 수도 있지만 1, 2, 3이 있을 경우 아직 합치지 않았으면 내가 속한 집합의 대표는 나 이기 때문이다.

 

따라서

int[] root = new int[n];
for (int i = 0; i < n; ++i) {
	root[i] = i;
}

와 같이 자신의 대표를 자신으로 먼저 설정해주어야 한다.

 

저기서는 지역변수로 설정해주었지만 root는 전역변수로 설정해두는 것이 나중에 매우 편할 것이다.왜냐하면 Find든 Union이든 root를 확인하고 호출하게 되는데 지역변수로 넘겨주어도 되지만 그건 생각보다 귀찮기 때문이다.

 

물론 이전 준환이의 양팔저울에서 언급하였지만 지역변수로 넘겨주는 것이 훨씬 더 좋은 성능을 내기 때문에 습관이 들었다면 지역변수로 하도록 하자

 

 

두번째 Find를 해보겠다.Find의 경우 너희 집단 대표가 누구니? 라고 묻는것인데1. 내 집단의 대표는 나다면 나라고 알려준다.

 

2. 보통 음 다른 블로그에서는 최악의 경우를 대비하여 다시 제일 위에 사람만 언급하는 경우도 있고 그렇지만   아시다시피 문제마다 사용해야하는 경우가 다르기 때문에 기본기에 충실하여 기본기를 익히고 나머지를 생각해서   짜보는 것을 추천한다.   이제 보여줄 아래의 코드에서는 바로 자신의 상관만 가르키게 되어있다.

 

예를 들어 3의 상관은 2이고 2의 상관은 1이라고 한다면3에게 너희 집단 대표가 누구야? 라고 물어보면 3은 2에게 물어보고 2는 1에게 다시 물어보고 1은 자기가 대표임으로 내가 대표입니다. 하고 답변해주는 것이다.

 

이를 코드로 나타내면 다음과 같다.

static int find(int x) {
	if (x != root[x])
		return find(root[x]);
	return x;
}

다른 블로그들을 보면 if else로 명확하게 구분을 해놓은 경우가 많은데... 굳이 그럴 필요가 있나 싶다.

무조건 그렇게 구별할 정도라면.... 이 글을 이해하는 것 조차 어려울 것이다.

 

세번째 유니온

유니온은 정말 간단하다 집단 대표끼리 만나 누가 내 밑으로 오니? 를 결정하는 것으로 이 규칙의 경우 여러분이 정하는 것이다.

하지만 "나"는 0 1 2 3 4 순으로 0이 대표를 하는 것이 이뻐보여 숫자가 작은것이 대표를 하도록 하였다.

 

static void union(int x, int y) {
	if (x < y) {
		root[y] = root[x];
	} else {
		root[x] = root[y];
	}
}

혹여나.... root[x]와 root[y]가 같을때는요 하고 물어볼 수도 있는데...

 

음 union을 호출하는 곳에서 그 경우를 대비해 놓았고 이 경우를 대비하지 않더라도 2의 상사는 1, 3의 상사가 1인데

3의 상사는 1로 하겠다고 덮어쓰는 것은 문제가 될 리가 없다.

 

마지막으로 Find와 Union을 잔뜩 호출할 while문을 소개하겠다.

while문의 경우 모든 경로를 다 해 볼 것이다.

 

혹여나 이해가 안가는 사람을 위해 자세히 설명하면

1, 2, 3 이라는 집단이 있다고 하자

(역시나 아까부터 설명했듯이 집단의 대표는 1이다 1->2->3 순으로 엮여 있다고 생각하면 된다)

여기서 4와 2가 길이 있다라고 나온다면 그냥 연결해주면 되지 않겠느냐 라고 말 할수 있지만

음.... 하나로 문제의 경우 1에서 4로 가는길이 멀더라도 연결만 되어있으면 된다...

아오 말이 점점 꼬이는데...피곤해서 그렇다... 어제 3시간 잤으니까...

 

잡소리는 그만하고 결론 부터 말하자면 1, 2, 3의 집단과 4를 연결해주는 것이다.

물론 4 와 2를 연결하는 비용을 지불하고 서 말이다. 

우리는 어디로든 통할 수 있게 길만 만들어주면 되기때문에 1, 2, 3 집단과 4를 연결해준 것이다.

 

만약 1과 4를 연결하는 도로가 있는데 2와 4를 연결하는 도로보다 비싸다고 하면 굳이 연결할 필요가 없다.

( 이해가 가도록 빈다... 이 글을 읽을 미래의 나에게도 )

 

자....

 

정말 이제 이 문제에 대해서만 말하면

1. 모든 도로를 구하고

2. 비용이 작은 도로부터 꺼내어서 연결해주는데 위에서 언급한 것처럼 1과 4를 연결하는 도로가 더 비싸다면

과감히 버린다.

 

이 부분의 경우

while (!pq.isEmpty()) {
	w = pq.poll();
	int x = find(w.node1);
	int y = find(w.node2);
	if (x == y)
		continue;
	union(x, y);
	cost += e * w.cost;
}

여기서 x == y 일 경우 continue 해주는 로직이 위에서 언급한 2번이다. 코드 전체가 나오지 않아 잘 모를 수도 있겠지만

1. PriorityQueue 를 사용하여 cost가 가장 작은 것 부터 나오게 하였고

2. 2와 4를 연결하는 도로가 연결되면 1의 root는 1, 4의 root는 2가 되는 것이다. 아닌가 1인가 ...?

   여튼 find를 하게되면 최종 대표님은 같다....

 

여러분들이 기다리던 전체 코드를 보여드리겠습니다. 너무 오랜만에 알고리즘을 공부하고 블로그도 포스팅 하다보니 신이 나서 주절주절 쓰게 되었네요 이 블로그만의 특징이 아닐까요 하하

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.PriorityQueue;

public class Solution1251 {
	static class Way implements Comparable<Way> {
		int node1, node2;
		double cost;

		Way(int node1, int node2, double cost) {
			this.node1 = node1;
			this.node2 = node2;
			this.cost = cost;
		}

		@Override
		public int compareTo(Way o) {
			return (int) (this.cost - o.cost);
		}
	}

	static int[] root;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int T = Integer.parseInt(br.readLine());
		for (int t = 1; t <= T; ++t) {
			int n = Integer.parseInt(br.readLine());
			double[] xArr = new double[n];
			double[] yArr = new double[n];
			String[] str = br.readLine().split(" ");
			for (int i = 0; i < n; ++i) {
				xArr[i] = Double.parseDouble(str[i]);
			}
			str = br.readLine().split(" ");
			for (int i = 0; i < n; ++i) {
				yArr[i] = Double.parseDouble(str[i]);
			}
			double e = Double.parseDouble(br.readLine());
			root = new int[n];
			for (int i = 0; i < n; ++i) {
				root[i] = i;
			}
			PriorityQueue<Way> pq = new PriorityQueue<Way>();
			for (int i = 0; i < n - 1; ++i) {
				for (int j = i + 1; j < n; ++j) {
					double disX = (xArr[i] - xArr[j]) * (xArr[i] - xArr[j]);
					double disY = (yArr[i] - yArr[j]) * (yArr[i] - yArr[j]);
					double dis = disX + disY;
					pq.offer(new Way(i, j, dis));
				}
			}
			Way w = null;
			double cost = 0;
			while (!pq.isEmpty()) {
				w = pq.poll();
				int x = find(w.node1);
				int y = find(w.node2);
				if (x == y)
					continue;
				union(x, y);
				cost += e * w.cost;
			}
			bw.write("#" + t + " " + Math.round(cost) + "\n");
		}
		bw.close();
		br.close();
	}

	static int find(int x) {
		if (x != root[x])
			return find(root[x]);
		return x;
	}

	static void union(int x, int y) {
		if (x < y) {
			root[y] = root[x];
		} else {
			root[x] = root[y];
		}
	}

}

자 필요하신 분은 긁어 쓰시든.... 참고만 하시든...하시면 됩니다.

 

아 그리고

☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆

비슷한 로직으로 했는데 답이 틀리다? 그러면 어차피 길이를 제곱해서 e를 곱해준 뒤에 더해줄꺼니까...

root 씌우지 마시고 그냥 두세요... 저도 한참을 해메었네요

★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★