[BOJ 1043] 거짓말 (Java)

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

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 List[] adjList=new ArrayList[51];
	static List<List<Integer>> parties;
	static boolean[] visited;
	static int N, M, K, cnt;
	static int[] knows;
	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());
		st=new StringTokenizer(br.readLine());
		K=Integer.parseInt(st.nextToken());
		knows=new int[K];
		for (int i=0; i<K; i++) {
			knows[i]=Integer.parseInt(st.nextToken());
		}
		int person;
		visited=new boolean[N+1];
		parties=new ArrayList<List<Integer>>(M);
		for (int i=0; i<M; i++) {
			st=new StringTokenizer(br.readLine());
			cnt=Integer.parseInt(st.nextToken());
			parties.add(new ArrayList<Integer>());
			for (int j=0; j<cnt; j++) {
				person=Integer.parseInt(st.nextToken());
				parties.get(i).add(person);
			}
			for (int j=0; j<cnt; j++) {
				int me=parties.get(i).get(j);
				if (adjList[me]==null) adjList[me]=new ArrayList<Integer>();
				for (int k=0; k<cnt; k++) {
					if (me!=parties.get(i).get(k)) {
						adjList[me].add(parties.get(i).get(k));
					}
				}
			}
		}
		for (int i=0; i<K; i++) {
			int known=knows[i];
			dfs(known);
		}
		int answer=0;
		for (int i=0; i<M; i++) {
			for (int j=0; j<parties.get(i).size(); j++) {
				if (!visited[parties.get(i).get(j)]) {
					answer++;
					break;
				}
			}
		}
		System.out.println(answer);
		
		
	}
	private static void dfs(int p) {
		visited[p]=true;
		if (adjList[p]==null) return;
		for (int i=0; i<adjList[p].size(); i++) {
			int neighbor=(int) adjList[p].get(i);
			if (!visited[neighbor]) {
				dfs(neighbor);
			}
		}
		
	}

}

처음엔 뭔가 union-find 같았으나.. 풀이방법이 뭔가 빡 떠오르지 않아서 dfs 로 풀었다.

검색해보니 union-find로 푸는게 더 간단해보인다.

 

1~N부터 인접 리스트를 만들고, 파티에 같이 참석하는 사람을 인접한 노드로 해서 리스트에 넣어준다.

이후 진실을 아는 사람들의 배열인 knows를 이용해, 그 번호에 대해서 DFS 탐색을 한다.

이웃이면서, 방문하지 않은 노드들을 모두 방문해주고 dfs 탐색 해준다.

 

이후 한 파티에 참석한 인원 중 미방문 상태가 있으면, 해당 파티에 대해 answer++을 해준다.  

 

그런데 이렇게 하면 너무 복잡한 풀이같아서.. union-find로 푸는게 훨 간단하다.

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_BOJ_1043 {
	static int N, M, K;
	static int[] knows;
	static int[] parents;
	public static void init() {
		for (int i=1; i<=N; i++) {
			parents[i]=i;
		}
	}
	public static int find(int i) {
		if (parents[i]==i) return i;
		return parents[i]=find(parents[i]);
	}
	
	public static void union(int a, int b) {
		int pa=find(a);
		int pb=find(b);
		if (pa!=pb) {
			parents[pa]=pb;
		}
	}
	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());
		st=new StringTokenizer(br.readLine());
		K=Integer.parseInt(st.nextToken());
		knows=new int[K];
		parents=new int[N+1];
		List<List<Integer>> parties=new ArrayList<>();
		init();
		for (int i=0; i<K; i++) {
			knows[i]=Integer.parseInt(st.nextToken());
		}
		for (int i=0; i<M; i++) {
			st=new StringTokenizer(br.readLine());
			int cnt=Integer.parseInt(st.nextToken());
			parties.add(new ArrayList<>());
			int p=Integer.parseInt(st.nextToken());
			parties.get(i).add(p);
			int team=find(p); 
			for (int j=1; j<cnt; j++) {
				p=Integer.parseInt(st.nextToken());
				union(team, p);	//같은 파티->같은 팀으로 묶기
				parties.get(i).add(p);
			}
		}
		int answer=0;
		for (int i=0; i<M; i++) {
			boolean isSameTeam=false;
			for (int j=0; j<parties.get(i).size(); j++) {
				int p=parties.get(i).get(j);
				for (int k=0; k<knows.length; k++) {
					if (find(knows[k])==find(p)) {	//knows와 같은 그룹에 속할 경우
						isSameTeam=true;
						break;
					}
				}
				if (isSameTeam) {
					break;
				}
			}
			if (!isSameTeam) {
				answer++;
			}
		}
		System.out.println(answer);
	}
		
}

union-find 적용해 다시 풀어본 풀이.