[BOJ] 1043 - 거짓말 (Java)

알고리즘

• 자료 구조
• 그래프 이론
• 그래프 탐색
• 분리 집합

1. 문제

• 파티에 참석하는 사람들 중에서 일부가 진실을 알고 있을 때, 최대 몇 개의 파티에서 거짓말을 할 수 있는지를 구하는 문제
  

2. Idea

• 파티의 참석자들을 같은 집합으로 묶어주고, 진실을 아는 사람들의 대표자를 찾아서 진실을 알고 있는 사람으로 표시
• 각 파티에서 첫 번째 사람의 대표자를 확인하여 진실을 알고 있는 사람이 아니라면 거짓말을 할 수 있는 파티로 판단

3. 풀이

3.1. 변수 선언 및 초기화

• N: 전체 사람의 수
• M: 전체 파티의 수
• total: 거짓말을 할 수 있는 파티의 수를 저장하는 boolean형 배열
• truePeople: 진실을 아는 사람들의 정보를 저장하는 배열입니다
  • 배열 크기는 51(진실을 아는 사람의 수가 0 이상 50 이하)
  • 인덱스: 사람의 번호
  • 번호의 사람이 진실을 알고 있다면 true, 아니면 false
• parent: Union-Find 자료구조에서 각 원소의 부모(대표자)를 나타내는 배열
  • 각 인덱스는 사람의 번호, 초기에는 자기 자신을 부모(대표자)로 설정
• Union-Find 초기화
  • 각 사람을 대표자로 하는 집합을 만들기 위해 Union-Find 자료구조를 초기화
  • 각 사람의 parent 배열 생성 및 초기 대표자(자기 자신) 설정

static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static int N, M, total = 0;
static boolean[] truePeople = new boolean[51];
static int[] parent;

...

  N = Integer.parseInt(st.nextToken()); // 사람 수 
  M = Integer.parseInt(st.nextToken()); // 파티 수

  // union-find 초기화 
  parent = new int[N+1];
  for(int i=1;i<=N; i++) {
      parent[i] = i;
  }

3.2. 진실을 아는 사람 정보 저장

• truePeople 배열을 만들어서 진실을 아는 사람들의 정보를 저장

// 진실을 아는 사람 정보 받아오기 truePeople[진실을아는사람] == true 
st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
for(int i=0; i<n; i++) {
	truePeople[Integer.parseInt(st.nextToken())] = true;
}

3.3. 파티 정보 저장 및 Union

• 각 파티의 참석자들을 저장하면서 동시에 같은 파티에 참석한 사람들을 Union-Find로 묶어준다.

// 파티 정보를 받아오면서 같은 파티에 있는 사람들 union
ArrayList<Integer>[] peoples = new ArrayList[M];
for(int i=0; i<M; i++) {
	peoples[i] = new ArrayList<>();
}
int value, pre =0;
for(int i=0; i<M; i++) {
	st = new StringTokenizer(br.readLine());
	n = Integer.parseInt(st.nextToken());
	if(n > 0) {
		pre = Integer.parseInt(st.nextToken());
		peoples[i].add(pre);
	}
	for(int j=1; j<n; j++) {
		value = Integer.parseInt(st.nextToken());
		peoples[i].add(value);
		union(pre, value); // 두명씩 union하면 모두가 같은 parent를 갖게 됨.
		pre = value;
	}
}

3.4. 진실을 아는 사람들 집합의 대표자(parent) 찾기

• 진실을 아는 사람들의 대표자를 찾아서 그 대표자를 진실을 알고 있는 사람으로 표시

// 진실을 아는 사람들의 parent는 같이 파티를 참여 했으므로 진실을 아는 사람들
int parent;
for(int i=1; i<truePeople.length; i++) {
	if(truePeople[i]) {
		truePeople[find(i)] = true;
	}
}

3.5. 거짓말을 할 수 있는 파티 찾기 및 결과 출력

• 각 파티에서 첫 번째 사람의 대표자(parent)를 찾아서, 그 대표자가 진실을 아는 사람이 아니면 total++
• 거짓말을 할 수 있는 파티의 최대 수인 total 출력

// 진실을 아는 사람들과 파티를 같이 하지 않았으면 total++
for(int i=0; i<M; i++) {
	if(peoples[i].size() > 0) {
		parent = find(peoples[i].get(0));
		if(!truePeople[parent]) total++;
	}
}

// 거짓말 할 수 있는 파티 최대 수 출력
System.out.println(total);

3.6. Union-Find (Disjoint Set)

• find: 주어진 원소의 대표자를 찾는 함수로 경로 압축을 통해 효율적으로 대표자 find
• union: 두 개의 원소가 속한 집합을 합치는 함수
  • 두 집합의 대표자를 비교하여 하나의 집합으로 union

private static boolean union(int a, int b) {
  a = find(a);
  b = find(b);

  if(a!= b) {
      if(a>b) {
          parent[a] = b;
      } else {
          parent[b] = a;
      }
      return true;
  }
  return false;
}

4. 전체코드

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

public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static int N, M, total = 0;
	static boolean[] truePeople = new boolean[51];
	static int[] parent;
	
	public static void main(String[] args) throws Exception {
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken()); // 사람 수 
		M = Integer.parseInt(st.nextToken()); // 파티 수
		
		// union-find 초기화 
		parent = new int[N+1];
		for(int i=1;i<=N; i++) {
			parent[i] = i;
		}
		
		// 진실을 아는 사람 정보 받아오기 truePeople[진실을아는사람] == true 
		st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		for(int i=0; i<n; i++) {
			truePeople[Integer.parseInt(st.nextToken())] = true;
		}
		
		// 파티 정보를 받아오면서 같은 파티에 있는 사람들 union
		ArrayList<Integer>[] peoples = new ArrayList[M];
		for(int i=0; i<M; i++) {
			peoples[i] = new ArrayList<>();
		}
		int value, pre =0;
		for(int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			n = Integer.parseInt(st.nextToken());
			if(n > 0) {
				pre = Integer.parseInt(st.nextToken());
				peoples[i].add(pre);
			}
			for(int j=1; j<n; j++) {
				value = Integer.parseInt(st.nextToken());
				peoples[i].add(value);
				union(pre, value); // 두명씩 union하면 모두가 같은 parent를 갖게 됨.
				pre = value;
			}
		}
		
		// 진실을 아는 사람들의 parent는 같이 파티를 참여 했으므로 진실을 아는 사람들
		int parent;
		for(int i=1; i<truePeople.length; i++) {
			if(truePeople[i]) {
				truePeople[find(i)] = true;
			}
		}
		
		// 진실을 아는 사람들과 파티를 같이 하지 않았으면 total++
		for(int i=0; i<M; i++) {
			if(peoples[i].size() > 0) {
				parent = find(peoples[i].get(0));
				if(!truePeople[parent]) total++;
			}
		}

		// 거짓말 할 수 있는 파티 최대 수 출력
		System.out.println(total);
	}
	
	private static int find(int x) {
		if(parent[x] == x) 
			return parent[x] = x;
		else  return find(parent[x]);
		
	}
	
	private static boolean union(int a, int b) {
		a = find(a);
		b = find(b);
		
		if(a!= b) {
			if(a>b) {
				parent[a] = b;
			} else {
				parent[b] = a;
			}
			return true;
		}
		return false;
	}
}