백준 1043 - 거짓말

Java

1043 번 - 거짓말

문제

N개의 사람 수와 M개의 파티 수가 주어진다.
지민이는 모든 파티에 참석하며, 각 파티마다 최대한 거짓말을 많이 하고 싶어한다.
하지만, 진실을 아는 사람이 존재하며 진실을 아는 사람과 같은 파티에 속한 사람들은 모두 진실을 알게 된다.
이때, 지민이가 거짓말쟁이로 알려지지 않으면서, 과장된 이야기를 할 수 있는 파티 개수의 최댓값을 구하는 프로그램을 작성하시오.

접근 방법

DisJoint Set으로 각 파티에 속한 사람들 끼리 묶는다.
묶은 뒤, 각 파티에 속한 사람들은 서로 Parent Node가 같게 된다.
다시 한번 파티의 사람들을 확인하며, 그 파티의 구성원들이 전부 진실의 아는 자와 다른 그룹이어서 Parent Node가 다른지 확인한다.
전부 다르면 결과를 증가 시킨다.

코드

import java.util.*;
import java.io.*;

public class Main {
	static int n, m, result;
	static int[] parents;
	static List<int[]> party;
	static List<Integer> truth;	// 진실을 아는 자
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk = new StringTokenizer(br.readLine());
    	n = stoi(stk.nextToken());
    	m = stoi(stk.nextToken());
    	
    	parents = new int[n + 1];
    	truth = new ArrayList<>();
    	party = new ArrayList<>();
    	
    	stk = new StringTokenizer(br.readLine());
    	int k = stoi(stk.nextToken());
    	int man;
    	// 진실을 아는 자를 세팅
    	for(int i = 0; i < k; i++) {
    		man = stoi(stk.nextToken());
    		truth.add(man);
    	}
    	
    	int[] partyMan;
    	// 파티 세팅
    	for(int i = 0; i < m; i++) {
    		stk = new StringTokenizer(br.readLine());
    		man = stoi(stk.nextToken());
    		partyMan = new int[man];
    		for(int j = 0; j < man; j++) {
    			partyMan[j] = stoi(stk.nextToken());
    		}
    		party.add(partyMan);
    	}
    	
    	// disjoint set으로 같은 파티에 온 사람끼리 묶는다
    	init();
    	
    	int a;
    	for(int i = 0; i < m; i++) {
    		partyMan = party.get(i);
    		a = partyMan[0];
    		for(int j = 1; j < partyMan.length; j++) {
    			union(a, partyMan[j]);
    		}
    	}
    	
    	// 각 파티에 참석한 사람이 진실의 아는자와 같은 파티에 있는지 확인
    	boolean isKnown;
    	for(int i = 0; i < m; i++) {
    		partyMan = party.get(i);
    		isKnown = false;
			// 각 파티를 탐색하여 파티 인원 중 진실을 아는 사람이 있는지 확인
    		for(int j = 0; j < partyMan.length; j++) {
    			if(chkInTruth(partyMan[j])) {
    				isKnown = true;
    				break;
    			}
    		}
    		if(!isKnown) {		// 아무도 진실을 모르면 정답 증가
    			result++;
    		}
    	}
    	
    	System.out.println(result);
    	br.close();
	}
	
	// 현재 사람의 root parent와 진실의 아는 사람의 root parent가 같은지 확인
	static boolean chkInTruth(int man) {
		for(int i : truth) {
			if(findSet(man) == findSet(i)) {
				return true;
			}
		}
		return false;
	}
	
	// --------- disjoint set -------
	static void init() {
		for(int i = 1; i <= n; i++) {
			parents[i] = i;
		}
	}
	
	static int findSet(int num) {
		if(parents[num] == num) {
			return num;
		}
		return parents[num] = findSet(parents[num]);
	}
	
	static boolean union(int a, int b) {
		int aRoot = findSet(a);
		int bRoot = findSet(b);
		if(aRoot == bRoot)
			return false;
		int min = Math.min(aRoot, bRoot);
		parents[aRoot] = min; 
		parents[bRoot] = min;
		return true;
	}
	
	
	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

후기

Disjoint Set을 응용한 문제

개선할 점

없습니다.