[백준] G4 1717번 집합의 표현 (JAVA)

문제 출처 - Baekjoon Online Judge

문제는 여기

1717번: 집합의 표현

[문제] 

초기에 {0}, {1}, {2}, ... {n} 이 각각 n+1개의 집합을 이루고 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다.

집합을 표현하는 프로그램을 작성하시오.

[입력]

첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 a가 포함되어 있는 집합과, b가 포함되어 있는 집합을 합친다는 의미이다. 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 1 a b의 형태로 입력이 주어진다. 이는 a와 b가 같은 집합에 포함되어 있는지를 확인하는 연산이다. a와 b는 n 이하의 자연수 또는 0이며 같을 수도 있다.

[출력]

1로 시작하는 입력에 대해서 한 줄에 하나씩 YES/NO로 결과를 출력한다. (yes/no 를 출력해도 된다)

 

 

---

[풀이]

1. parents 배열을 만들어서 자기 자신의 값을 넣어준다.

2. 합집합을 해야한다면 parents배열에 연결된 정보를 준다. (A, B가 있다면 parents[B] = A)

3. 포함관계인지 확인을 할 때는 두 값의 parents의 값을 보고 같다면 포함 관계이다.

[접근]

1. 처음에 인접 배열을 만들어서 처리할려고 했다.

 - 이차원 배열을 만들어 주고 연결이 될 경우 1로 표시를 해주는 방식

 - 하지만 메모리 초과 발생

2. 메모리 초과가 나지 않도록 서로소 방법을 사용해서 구현했다.

[코드]

인접 배열 사용 - 결과는 Fail

package BOJ_gold;

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

public class Main_G4_1717_array_memory_leak {
	static int n;
	static int m;
	static int map[][];

	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());
		m = Integer.parseInt(st.nextToken());
		
		map = new int[n + 1][n + 1];
		
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (i == j)
					map[i][j] = 1;
			}
		}
		
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			
			int op = Integer.parseInt(st.nextToken());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			
			if (op == 0)
				map[a][b] = map[b][a] = 1;
			else if (op == 1) {
				if (map[a][b] == 1)
					System.out.println("YES");
				else if (map[a][b] == 0)
					System.out.println("NO");
			}
		}
	}
}

 

서로소 사용 - 결과는 Accept

package BOJ_gold;

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

public class Main_G4_1717_union {
	static int n;
	static int m;
	static int parents[];

	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());
		m = Integer.parseInt(st.nextToken());
		
		parents = new int[n + 1];
		
		makeSet();
		
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			
			int op = Integer.parseInt(st.nextToken()); // 연산
			int a = Integer.parseInt(st.nextToken()); // a
			int b = Integer.parseInt(st.nextToken()); // b
			
			// 0이라면 합집합
			if (op == 0) {
				union(a, b);
			}
			else if (op == 1) { // 1이라면 포함관계 확인
				check(a, b);
			}
		}
	}
	
	// 배열 초기화
	public static void makeSet() {
		for (int i = 0; i <= n; i++) {
			parents[i] = i;
		}
	}
	
	// parents의 값을 찾기
	public static int find(int i) {
		if (parents[i] == i)
			return i;
		
		return parents[i] = find(parents[i]);
	}
	
	// 두개를 결합시키기
	public static void union(int i, int j) {
		i = find(i);
		j = find(j);
		
		if (i != j) {
			parents[j] = i;
		}
	}
	
	// 포함관계인지 확인
	public static void check(int i, int j) {
		i = find(i);
		j = find(j);
		
		if (i == j)
			System.out.println("YES");
		else
			System.out.println("NO");
	}
}