[JAVA] 백준 1043 - 거짓말

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

M개의 파티가 열릴 때, 진실을 말해야하는 사람이 포함된 파티에 참석한 모든 인원을 진실을 말해야 하는 사람으로 업데이트하며 최종적으로 과장된 이야기를 할 수 있는(진실을 말해야하는 사람이 없는) 파티의 개수를 구하는 문제이다.

사실 어떤 알고리즘을 썼다기보단 그냥 HashSet에 진실을 말해야하는 사람의 번호를 업데이트해가며 풀었다. 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Solved1043 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] a = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int mCount = a[0]; //사람의 수
        int pCount = a[1]; //파티의 수
        HashSet<Integer> tSet = new HashSet<>(); //진실을 말해야하는 사람을 저장하는 HashSet
        a = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        if (a[0] >= 1) {
            for (int i = 1; i < a.length; i++) {
                tSet.add(a[i]);
            }
        }
        HashMap<Integer, List<Integer>> map = new HashMap<>(); //파티 key, 참여인원 리스트를 저장하는 HashMap

        for (int i = 0; i < pCount; i++) {
            a = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            List<Integer> temp = new ArrayList<>();
            boolean flag = false;
            for (int j = 1; j < a.length; j++) {
                if (tSet.contains(a[j])) { //파티 참여 인원 중 진실을 말해야하는 사람이 존재하면 flag = true
                    flag = true;
                }
                temp.add(a[j]);
            }
            if (flag) {
                tSet.addAll(temp); //진실을 말해야하는 사람이 존재하는 파티라면 모든 참여인원에게 추후 진실을 말해야함
            }
            map.put(i, temp);
        }
        int answer = 0;
        for (int k = 0; k < pCount; k++) { 
        // 1,2 -> 2,3 -> 3,4 -> 4,5 순서쌍처럼 최대 pCount번에 걸쳐서 
        // 연쇄적으로 진실을 말해야하는 사람 리스트를 갱신해줘야할 수 있음
            for (int i = pCount - 1; i >= 0; i--) {
                boolean flag = false;
                for (Integer t : tSet) {
                    if (map.get(i).contains(t)) { //파티 참여 인원 중 진실을 말해야하는 사람이 존재하면 flag = true
                        flag = true;
                        break;
                    }
                }
                if(flag){
                    tSet.addAll(map.get(i)); //진실을 말해야하는 사람이 존재하는 파티라면 모든 참여인원에게 추후 진실을 말해야함
                }
            }
        }
        for (int i = pCount - 1; i >= 0; i--) {
            boolean flag = false;
            for (Integer t : tSet) {
                if (map.get(i).contains(t)) {
                    flag = true;
                    break;
                }
            }
            if(!flag){
                answer++; //모든 사람이 과장된 내용을 들어도 되는 사람인 경우 answer++
            }
        }
        System.out.println(answer);
    }
}

 

질문 게시판을 살펴보니 Union-find라는 알고리즘을 사용했다는데, 이 알고리즘을 잘 몰라서 GPT한테 물어봤다.

사람들을 각각 노드로 생각하고(부모 노드가 없으므로 자기 자신을 부모로 초기설정), 각 파티에 참여한 첫번째 사람을 root노드로 지정하고 나머지 사람을 leaf 노드로 붙였을 때, 1~n번째 사람(노드)들의 부모는 1번째 사람이 된다.

다음 파티를 이어가면서 각 파티 사람들의 root를 검색했을 때 root가 다른 경우가 있다면 각 파티의 0번째 사람의 root에 leaf노드로 붙여간다.

모든 파티를 조회한 이후 초기에 주어진 진실을 아는 사람들의 root값과 모든 사람들의 root값을 비교할 수 있는데, 모든 파티 참여자의 root가 진실을 아는 사람들의 root값과 다른 파티의 개수를 구하면 과장된 내용을 말해도 되는 파티의 개수를 구할 수 있다.