Union Find [BOJ1976] 여행가자

드디어 이해해버렸다 유니온 파인드....

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

무슨 문제?

문제의 요점은 여행의 순서가 아니라 여행지들이 모두 이어져 있는지 이다.

이어져만 있으면 어떤 지점을 경유해서 어떻게든 그 지점으로 갈 수 있기 때문이다. 결론적으로
disjoint set , 즉 노드간의 연결을 통해 만나는 서로소인지, 아닌지를 판별하여, 여행 경로중에 서로소 집합에 속한 경우가 있으면 NO, 아니면 YES를 출력하면 된다.

풀이

입력에서 연결이 주어질 때, union을 통해 같은 부모를 바라보도록 한다. 서로의 부모가 현재 다른 상태이면 무조건 더 작은 값(인덱스)를 가지는 것을 부모로 하도록 한다.

	private static void unionParent(int i, int j) {
		int iParent = find(i);
		int jParent = find(j);
		int parentVal = Math.min(iParent, jParent);
		parent[iParent] = parentVal;
		parent[jParent] = parentVal;

	}

여기서 find 함수는 부모를 찾는 함수로, 자기 자신이 부모일 때까지 재귀적으로 탐색한다.

	private static int find(int i) {
		if (parent[i] == i)
			return i;
		else
			return (find(parent[i]));
	}

주의할 점

원래 unionParent 함수에서 실수를 했었는데, 원래는

parent[i] = parentVal;
parent[j] = parentVal;

로 내 부모의 부모값을 바꿔주는 것이 아닌 나의 부모만을 바꿔줘서, 내 부모의 부모(자기자신)이 자식의 부모(바뀐 parentVal) 보다 클 수 있기 때문에 나는 기존의 부모를 바라보고, 내 부모가 새롭게 갱신된 부모를 바라보면

최종적으로 모두 같은 부모를 바라보게 되므로 합집합에 속할 수 있다.

최종 코드

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

public class BOJ1976_여행가자 {

	static int N, M;
	static int[] parent;
	static boolean isPossib = true;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		N = Integer.parseInt(br.readLine());
		M = Integer.parseInt(br.readLine());
		parent = new int[N + 1];

		for (int i = 1; i <= N; i++) {
			parent[i] = i;
		}

		for (int i = 1; i <= N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 1; j <= N; j++) {
				if (Integer.parseInt(st.nextToken()) == 1) {
					unionParent(i, j);
				}
			}
		}

		st = new StringTokenizer(br.readLine());

		int parentVal = find(Integer.parseInt(st.nextToken()));
		for (int i = 1; i < M; i++) {
			if (parentVal != find((Integer.parseInt(st.nextToken())))) {
				isPossib = false;
				break;
			}
		}

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

	private static void unionParent(int i, int j) {
		int iParent = find(i);
		int jParent = find(j);
		int parentVal = Math.min(iParent, jParent);
		parent[iParent] = parentVal;
		parent[jParent] = parentVal;

	}

	private static int find(int i) {
		if (parent[i] == i)
			return i;
		else
			return (find(parent[i]));
	}

}