[백준 / Java] 1043번 : 거짓말

 

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

---

◎ 문제

---

◎ 코드 및 풀이

 

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

public class Main{
	static int[] parents;
	static List<Integer> kList;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st ;
		
		st = new StringTokenizer(br.readLine());
		
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		
		parents = new int[n+1];
		for(int i=1; i<n+1; i++) {
			parents[i] = i;
		}
		
		st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		kList = new ArrayList<>();
		if(N==0) {
			System.out.println(m);
			return;
		} else {
			for(int i=0; i<N; i++) {
				kList.add(Integer.parseInt(st.nextToken()));
			}
		}
		
		List<Integer>[] partyList = new ArrayList[m];
		for(int i=0; i<m; i++) {
			partyList[i] = new ArrayList<>();
		}
		
		for(int i=0; i<m; i++) {
			st = new StringTokenizer(br.readLine());
			int pn = Integer.parseInt(st.nextToken());
			int x = Integer.parseInt(st.nextToken());
			
			partyList[i].add(x);
			for(int j=1; j<pn; j++) {
				int y = Integer.parseInt(st.nextToken());
				union(x,y);
				partyList[i].add(y);
			}
		}
		
		int cnt = 0;
		for(int i=0; i<m; i++) {
			boolean flag = false;
			for(int num : partyList[i]) {
				if(kList.contains(find(num))) {
					flag = true;
					break;
				}
			}
			if(!flag) {
				cnt++;
			}
		}
		
		System.out.println(cnt);
		
		
	}
	
	
	static int find(int x) {
		if(parents[x]==x) {
			return x;
		}
		return find(parents[x]);
	}
	
	static void union(int x,int y) {
		int px = find(x);
		int py = find(y);
		if(kList.contains(py)) {
			int tmp = px;
			px = py;
			py = tmp;
		}
		parents[py] = px;
	}
}

 

DFS나 BFS로 풀 수 도 있는 문제이지만 새로운 알고리즘을 배워보기 위해 유니온 파인드 알고리즘을 사용했다.

---

◎ 기록

 

유니온 파인드(Union Find)

그래프 알고리즘으로 두 노드가 같은 그래프에 속하는지 판별하는 알고리즘

find(int x) -> x의 최상위 부모 노드를 찾는 메서드

union(int x, int y) -> x와 y의 최상위 부모 노드를 연결하는 메서드