백준 1717번 자바

1. 문제

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

1717번: 집합의 표현

 

2. 접근방식

유니온 파인드를 활용해 해결하면 된다.

 

유니온 파인드란?

일반적으로 여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union연산과 두 노드가 같은 집합에 속해 있는지 확인하는 find 연산으로 구성되어 있는 알고리즘

 

왜 쓰는지?

유니온 파인드 알고리즘에서 find 연산은 시간 복잡도를 줄이는 역할을 한다. find 연산을 하면 노드간의 경로를 압축 시키기 때문에 시간 복잡도가 O(1)로 변경된다.

 

1 -> 2 -> 3 -> 4의 노드 관계는 루트노드가 4인데, 1에서 부터 탐색을 하면 2,3을 순차적으로 거쳐야만 루트노드에 도달할 수 있다. 하지만 find 연산을 수행하고 나면 1,2,3 노드가 루트노드 4에 직접연결이 된다.

 

3. 구현

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	static int n,m;
	static int[] arr;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		arr = new int[n+1];
		for (int i=0; i<arr.length; i++) {
			arr[i] = i;
		}
		for (int i=0; i<m; i++) {
			st = new StringTokenizer(br.readLine());
			int calculation = Integer.parseInt(st.nextToken());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			
			if (calculation == 0) {
				union(a, b);
				continue;
			}
			
			a = find(a);
			b = find(b);
			if (a == b) {
				System.out.println("yes");
			} else {
				System.out.println("no");
			}
		}
	}
	
	public static void union(int a, int b) {
		int first = find(a);
		int second = find(b);
		if (first != second) {
			arr[second] = first; 
		}
	}
	
	public static int find(int element) {
		if (arr[element] == element) {
			return element;
		} else {
			return arr[element] = find(arr[element]);
		}
	}
}

 

4. 정리

로직엔 이상이 없는거 같은데 자꾸 틀렸습니다가 떴다. 이유는 find 연산에서 arr[element] != element가 다른 경우, 즉 루트노드가 아닌 경우에 해당 노드의 값을 find 연산을 통해 루트 노드의 값을 넣어주지 않았기 때문이었다.