[Baekjoon/Java] 1717번 집합의 표현

문제

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

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

 

입력

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

 

문제 풀이

 

어떻게 한 문제에서 저렇게 많은 오류들을 볼 수 있을까?이 문제는 내가 기술 블로그 <알고리즘 편>을 쓰게 한 장본인이다.처음엔 유니온파인드로 풀어야 되는지도 모르고 나름대로 열심히 풀었는데 난생 처음 보는 에러를 만났다.

 

첫번째 풀이 - 런타임 에러(ConcurrentModification)

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		StringBuilder sb = new StringBuilder();
		
		int n = sc.nextInt();
		int m = sc.nextInt();
		
		ArrayList<HashSet<Integer>> set = new ArrayList<HashSet<Integer>>();
		for(int i=0; i<=n; i++) {
			set.add(new HashSet<Integer>());
			set.get(i).add(i);
		}
		
		for(int i=0; i<m; i++) {
			int num = sc.nextInt();
			int a = sc.nextInt();
			int b = sc.nextInt();
			
			if(num == 0) {
				HashSet<Integer> temp = set.get(a);
				HashSet<Integer> temp2 = set.get(b);
				
				for(Integer value: temp) {
					set.get(value).addAll(set.get(b));
				}
				for(Integer value: temp2) {
					set.get(value).addAll(set.get(a));
				}
				set.get(a).addAll(set.get(b));
				set.get(b).addAll(set.get(a));
			}else {
				if(set.get(a).contains(b)) {
					sb.append("YES").append("\n");
				}else {
					sb.append("NO").append("\n");
				}
				
			}
		}
		System.out.println(sb);
	}
}

 

처음 생각했던 방법은 ArrayList<HashSet<Integer>> 와 같은 형태로 만들어서 각각의 ArrayList에 해당 인덱스 번호를 넣고 시작하는 것이었다. set을 선택한 이유는 중복을 제거하기 위해서였다.

 

나도 처음 써보는 구조였는데 bfs 풀 때 인접리스트가 생각나서 인접셋(?)을 만들었다.

 

그리고 m번 만큼 반복문을 돌면서 ArrayList의 해당하는 위치(a)의 HashSet을 뽑아서 HashSet 방문하며 b의 값을 추가했다. 반대도 마찬가지로 진행했다.(a <-> b)

 

내가 생각한 구조는 위의 사진과 같았다.

중복되기 때문에 비효율적일거라고 생각은 했지만 떠오르는 풀이는 이 뿐이라서 제출을 했는데 보도 듣도 못 한 에러를 만났다. ㅠ

 

 

두번째 풀이 - 시간 초과

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
	static int[] array;
	static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		int m = sc.nextInt();
		array = new int[n+1];
		
		for(int i=0; i<=n; i++) {
			array[i] = i;
		}
		
		for(int i=0; i<m; i++) {
			int num = sc.nextInt();
			int a = sc.nextInt();
			int b = sc.nextInt();
			
			if(num == 0) {
				union(a,b);
			}else {
				if(array[a] == array[b]) {
					sb.append("YES").append("\n");
				}else {
					sb.append("NO").append("\n");
				}
			}	
		}
//		System.out.println(Arrays.toString(array));
		System.out.println(sb);
	}

	private static void union(int a, int b) {
		int A = find(a);
		int B = find(b);
		if(A == B) {
			return;
		}else {
			if(A > B) {
				int tmp = array[a];
				for(int i=0; i<array.length; i++) {
					if(array[i] == tmp) {
						array[i] = array[b];
					}
				}
				array[a] = array[b];
			}else {
				int tmp = array[b];
				for(int i=0; i<array.length; i++) {
					if(array[i] == tmp) {
						array[i] = array[a];
					}
				}
				array[b] = array[a];
			}
		}
	}

	private static int find(int num) {
		if(array[num] == num) return num;
		return find(array[num]);
	}
}

 

나와 같은 에러가 난 사람이 있는지 질문게시판에서 찾아보다가 이 문제는 '유니온파인드'로 풀어야한다는 내용을 봤다.

유니온파인드에 대해 들어는 봤지만 한 번도 써본 적이 없고 어떻게 구현하는지도 몰랐다. 그래서 유니온파인드에 대해 공부하고(유니온파인드에 대한 블로그는 추후 작성 예정 ^^*) 적용했는데 시간 초과가 떴다.

 

 

세번째 ~ 풀이 - 메모리 초과, 틀렸습니다, 시간초과, 런타임에러(NoSuchElement)

메모리 초과

메모리 초과는 array를 잘못 출력해서 생긴 오류였다.

 

틀렸습니다

처음엔 시간 초과가 뜨는게 array의 길이만큼 반복문을 돌아서 그런 줄 알고 정답이 아닐 걸 알면서도 혹시?라는 생각에 반복문을 삭제했다.

그리고 내가 생각했을 때는 array[a] == array[b] 일 때만 YES를 출력하는 것이라고 생각했는데 다른 풀이를 보니 find(a) == find(b) 일 때 YES를 출력하는 것이었다.

이해가 안 갔었다. 이유는 나는 어차피 7의 부모 노드는 1이 되는거 아닌가? 했는데 그게 아니라 7의 부모 노드는 6이고 6의 부모 노드 ... 이렇게 올라가서 최종 노드를 find 함수로 찾아서 비교하는 것이었다.

나는 무조건 7의 부모 노드는 1로 만들어야겠다는 생각에 첫번째 풀이와 같은 형태로 만들기 위해 노력했는데 ... 좀 짧은 생각이었다.

 

시간 초과

다른 사람들이 작성한 코드를 참고하며 수정했는데 또 시간 초과가 나버렸다.

이유는 '경로 압축'을 안했기 때문인데 이 때까지만 해도 아직까지 고집하던 입력 방식인 Scanner 때문인 줄 알았다.

그래서 Buffer로 바꿨는데도 시간 초과가 났다.

 

 

최종 풀이

시간 초과가 났던 문제는 find 함수에서 경로 압축을 안 했기 때문이었다.

경로압축최적화 : Find 함수 작성 시, return하는 값은 Find 함수 값을 검사하고 있는 노드에 넣어주는 것.

 

아 그리고 나는 유니온파인드 문제를 처음 풀어봐서 어떻게 union이 되는건지 감이 안 잡혔는데 직접 그려보니 이해가 되는 것 같았다.(잘못된 거 있으면 지적 부탁합니당 ㅎ)

 

 

코드

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

public class Main {
	static int[] array;
	static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		array = new int[n+1];
		
		for(int i=0; i<=n; i++) {
			array[i] = i;
		}
		
		for(int i=0; i<m; i++) {
			st = new StringTokenizer(br.readLine());
			int num = Integer.parseInt(st.nextToken());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			
			if(num == 0) {
				union(a,b);
			}else {
				if(find(a) != find(b)) {
					sb.append("NO").append("\n");
				}else {
					sb.append("YES").append("\n");
				}
			}
		}
		System.out.println(sb);
	}

	private static void union(int a, int b) {
		a = find(a);
		b = find(b);
		if(a > b) {
			array[a] = b;
		}else {
			array[b] = a;
		}
		
	}

	private static int find(int num) {
		if(array[num] == num) return num;
		return array[num] = find(array[num]);
	}
}

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