Baekjoon - 1717

문제

Solved.ac Gold5

UnionFind

위와 같은 문제를 풀 때 적용하는 방식이다

예시에 따라 입력하면 아래와 같은 순서로 변환하게 된다.
초기에는 모두 자기 자신을 가리키고 있다가 둘이 합치면(Union) 둘중 하나의 부모로 설정해 준다.

1차시도

public class Main {
	private static final String YES = "YES";
	private static final String NO = "NO";
	private static int[] data;
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();

		int[] init = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
		int countOfCalculation = init[0];
		int countOfLine = init[1];

		data = new int[countOfCalculation + 1];
		for (int i = 1; i < countOfCalculation + 1; i++) {
			data[i] = i;
		}

		for (int i = 0; i < countOfLine; i++) {
			int[] read = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
			int v1 = read[1];
			int v2 = read[2];
			if (read[0] == 0) { // 입력
				if (v1 != v2) {
					if (v1 > v2) {
						changeParents(v1, v2);
					} else {
						changeParents(v2, v1);
					}
				}
			} else { // 확인
				int parents1 = findParents(v1);
				int parents2 = findParents(v2);
				if (parents1 == parents2) {
					sb.append(YES).append("\n");
				} else {
					sb.append(NO).append("\n");
				}
			}
		}
		System.out.println(sb);

	}

	private static void changeParents(int target, int value) {
		if (data[target] != target) {
			int parents = findParents(target);
			changeParents(parents, value);
		} else {
			data[target] = value;
		}
	}

	private static int findParents(int target) {
		while (data[target] != target) {
			target = data[target];
		}
		return target;
	}

}

시간초과

2차시도

if (read[0] == 0) { // 입력
				int v1Parents = findParents(v1);
				int v2Parents = findParents(v2);
				if (v1Parents > v2Parents) {
					data[v1Parents] = v2Parents;
				} else {
					data[v2Parents] = v1Parents;
				}

입력 시 부모를 찾아와 부모만 변경함으로써 변경 가능하도록 수정하였습니다

시간초과(1차시도 보다는 진전)

경로 압축

문제점

먼저 위에서 부모를 검색하는 매서드를 살펴보면

private static int findParents(int target) {
		while (data[target] != target) {
			target = data[target];
		}
		return target;
	}

이렇게 나와있다.
이렇게 되면 최악의 경우 아래와 같이 구성되는 상황이 발생하고
그러면 맨 마지막 child에서 검색시 root까지 모든 부모를 따라 검색해야한다.

경로 압축

if (target == data[target]) {
		return target;
	}

	return data[target] = findParents(data[target]);
}

경로 압축을 하게 되면 위처럼 일어난다.
한번 검색한 child의 부모는 return문에서 처럼 값을 새로 지정하게 된다.
이러면 한번이라도 검색한 노드는 추후에 검색시 시간복잡도가 $O(1)$ 이 된다.

5차시도

public class Main {
	private static final String YES = "YES";
	private static final String NO = "NO";
	private static int[] data;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();

		int[] init = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
		int countOfCalculation = init[0];
		int countOfLine = init[1];

		data = new int[countOfCalculation + 1];
		for (int i = 1; i < countOfCalculation + 1; i++) {
			data[i] = i;
		}

		for (int i = 0; i < countOfLine; i++) {
			int[] read = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
			int v1 = read[1];
			int v2 = read[2];
			if (read[0] == 0) { // 입력
				int v1Parents = findParents(v1);
				int v2Parents = findParents(v2);
				if (v1Parents > v2Parents) {
					data[v1Parents] = v2Parents;
				} else {
					data[v2Parents] = v1Parents;
				}
			} else { // 확인
				int parents1 = findParents(v1);
				int parents2 = findParents(v2);
				if (parents1 == parents2) {
					sb.append(YES).append("\n");
				} else {
					sb.append(NO).append("\n");
				}
			}
		}
		System.out.println(sb);

	}

	private static int findParents(int target) {
		// while (data[target] != target) {
		// 	target = data[target];
		// }
		// return target;
		if (target == data[target]) {
			return target;
		}

		return data[target] = findParents(data[target]);
	}

}

성공