백준 1043번 자바 ☆

1. 문제

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

1043번: 거짓말

 

2. 접근 방식

유니온 파인드 방식으로 접근하면 된다. 

다만 문제를 풀면서 많이 헤맸던 부분의 반례 테케 하나를 아래에 첨부한다.

10 10
1 1
2 10 1
2 9 2
2 8 3
2 7 4
2 6 5
2 5 7
2 4 8
2 3 9
2 2 10
1 1

 

1번째 파티부터 N번째 파티까지 순차적으로 union연산을 하며 partyPeople의 요소들을 합집화한다. 그렇기 때문에 같은 집합이지만 find연산이 실행이 안되어서 해당 노드의 값이 루트 노드 값이 아닌 경우가 생긴다. 

 

그래서 진실을 아는 사람인지 아닌지 구분할 때 find연산을 사용해 루트노드의 값을 비교해줘야한다. 해당 부분에서 너무 헤맸다..

 

3. 구현

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

public class Main1043_1 {

	static int N,M;
	static int[] partyPeople;
	static List<int[]> parties; // 파티별 참가인원
	static int[] truePeople; // 진신을 아는 사람 그룹
	static int cnt;
	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());
		partyPeople = new int[N+1];
		parties = new ArrayList<int[]>();
		for (int i=1; i<=N; i++) {
			partyPeople[i] = i;
		}
		st = new StringTokenizer(br.readLine());
		int truePeopleSize = Integer.parseInt(st.nextToken());
		if (truePeopleSize == 0) {
			System.out.println(M);
			return;
		}
		truePeople = new int[truePeopleSize];
		for (int i=0; i<truePeopleSize; i++) {
			truePeople[i] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(truePeople); // 항상 작은 숫자를 루트 노드로 만들기 위해서 정렬
		int firstPerson = truePeople[0];
		
        // 진실을 아는 사람들의 루트노드 값을 가장 작은 숫자의 사람으로 만들어 그룹핑
        for (int i=1; i<truePeopleSize; i++) {
			partyPeople[truePeople[i]] = firstPerson;
		}
		for (int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			int party = Integer.parseInt(st.nextToken());
			parties.add(new int[party]);
			int pre = -1;
			for (int j=0; j<party; j++) {
				int current = Integer.parseInt(st.nextToken());
				parties.get(parties.size()-1)[j] = current;
				union(current, pre);
				pre = current;
			}
		}
		for (int[] party : parties) {
			boolean check = false;
			for (int person : party) {
            	// find연산을 안한 노드들이 있어 find연산으로 루트노드값을 비교
				if (find(firstPerson) == find(person)) {
					check = true;
				}
			}
			if (!check) {
				cnt++;
			}
		}
		
		System.out.println(cnt);
	}
	
	public static void union(int a, int b) {
		if (b == -1) {
			return;
		}
		int first = find(a);
		int second = find(b);
		if (first != second) {
			if (first > second) {
				partyPeople[first] = partyPeople[second];				
			} else {
				partyPeople[second] = partyPeople[first];
			}
		}
	}
	
	public static int find(int node) {
		if (partyPeople[node] == node) {
			return partyPeople[node];
		} else {
			return partyPeople[node] = find(partyPeople[node]);
		}
	}
}

 

4. 정리

좀만 생각해보면 쉽게 찾을 수 있는 반례였는데 집중을 잘못해 많이 헤맸다. 집중 집중!