[BOJ][JAVA] 1717번: 집합의 표현, 1976번: 여행가자

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

1717번: 집합의 표현

푸는 동안 사고과정 및 개선점

유니온 파인드를 적극적으로 활용하면 되는 문제다. 이전에 풀었던 문제인데 복습삼아 한번 더 풀어봤다.

유니온파인드는 make, find, union 세 단계로 구분하면되는데, 각각 살펴보자.

	public static void make() {
		p = new int[n + 1];
		for (int i = 0; i <= n; i++) {
			p[i] = i;
		}
	}

	public static int find(int a) {
		if (p[a] == a)
			return a;

		return p[a] = find(p[a]);
	}

	public static boolean union(int a, int b) {
		int pa = find(a);
		int pb = find(b);

		if (pa == pb)
			return false;
		p[pb] = pa;
		return true;
	}

make는 그냥 i번째 부모가 i라는 것을 알게 해주는 것이다. 준비단계라고 보면 된다. 

find가 핵심로직이기 때문에 union먼저 보자.

	public static boolean union(int a, int b) {
		int pa = find(a);
		int pb = find(b);

		if (pa == pb)
			return false;
		p[pb] = pa;
		return true;
	}

비교 대상 두 개를 갖고, 각각의 root를 갖고온다. 정확히는 어느 집합에 속해있는 지를 찾는다. 그게 pa = find(a)과정이다. 

만약 같은 집합에 속해있으면 union하지 않고, 다른 집합에 속해있다면 이제 집합에 포함시켜줘야한다. 이건 구현방식의 차이인데, 나는 첫번 째 인자를 부모, 두번째 인자를 자식후보 로 생각하고 union을 짠다.

b가 가리키는 집합이 a가 가리키는 집합을 가리키게 하면 이제 a와 b는 같은 집합을 가리키게 되고 union이 발생했으므로 true를 가리킨다.

true, false를 반환하는 이유는 같은 집합인지, 아닌지를 판별할 수 있게 하기 위함이다. 

이제 find를 보자.

	public static int find(int a) {
		if (p[a] == a)
			return a;

		return p[a] = find(p[a]);
	}

a의 집합(p[a])이 a 자신이라면 그냥 a를 반환하면 되고, 만약 그게 아니면 a가 가리키는 집합이 p[a]가 가리키는 집합을 재귀적으로 넣어서 결과적으로 depth가 1인 집합이 만들어지도록 하는 방법이다.

 

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

1976번: 여행 가자

유니온 파인드를 사용해서 이 문제를 풀어봤는데, 이 문제에서 중요한 점은 도시 번호가 1부터 시작한다는 점이다. 아무생각없이 zero-base로 유니온파인드를 설정하면 틀리게 되는 문제다..!

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

public class Main {
	static int[] p;
	static int n;

	static void make() {
		p = new int[n + 1];
		for (int i = 0; i < n; i++) {
			p[i] = i;
		}
	}

	static int find(int a) {
		if (p[a] == a)
			return a;
		return p[a] = find(p[a]);
	}

	static void union(int a, int b) {
		int pa = find(a);
		int pb = find(b);
		if (pa != pb) {
			p[pb] = pa;
		}
	}

	public static void main(String[] args) throws Exception {
		// System.setIn(new FileInputStream("res/input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		make();
		int target = Integer.parseInt(br.readLine());
		for (int i = 1; i <= n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			for (int j = 1; j <= n; j++) {
				int tmp = Integer.parseInt(st.nextToken());
				if (tmp == 1) {
					union(i, j);
				}
			}
		}
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int start = find(Integer.parseInt(st.nextToken()));
		boolean flag = true;
		if (st.hasMoreTokens()) {
			for (int i = 0; i < target - 1; i++) {
				int tmp = Integer.parseInt(st.nextToken());
				if (start != find(tmp)) {
					flag = false;
					break;
				}
			}
		}

		if (flag) {
			System.out.println("YES");
		} else {
			System.out.println("NO");
		}
	}
}

 

---

정답코드

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

public class Main {
	static int[] p;
	static int n;

	public static void make() {
		p = new int[n + 1];
		for (int i = 0; i <= n; i++) {
			p[i] = i;
		}
	}

	public static int find(int a) {
		if (p[a] == a)
			return a;

		return p[a] = find(p[a]);
	}

	public static boolean union(int a, int b) {
		int pa = find(a);
		int pb = find(b);

		if (pa == pb)
			return false;
		p[pb] = pa;
		return true;
	}

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		make();
		StringBuilder sb = new StringBuilder();

		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int target = Integer.parseInt(st.nextToken());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			if (target == 0) {
				// union
				union(a, b);
			} else {
				if (find(a) == find(b)) {
					sb.append("YES").append("\n");
				} else {
					sb.append("NO").append("\n");
				}
			}
		}
		System.out.println(sb);
	}

}

 

 

도움이 됐다면 댓글이나 공감 버튼 한 번씩 누르고 가주세요! 로그인 안해도 됩니다 ^_^