BOJ 1043 거짓말 by Java

문제 풀이 날짜: 2025-09-10

💡Github URL

https://github.com/ejjem/coding-test/tree/main/%EB%B0%B1%EC%A4%80/Gold/1043.%E2%80%85%EA%B1%B0%EC%A7%93%EB%A7%90

💡분류

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

💡알고리즘 설계

UnionFind 구현 → 파티에 같이 참여한 적이 있어 접점이 있는 사람들을 같은 그룹으로 묶음.

모든 파티 입력이 끝나고 나서, 각 파티에 대표 인원 1명씩 root를 검사해서(어차피 같은 파티에 참여한 인원은 반드시 같은 root) 진실을 아는 인원들의 root와 같으면 해당 파티는 거짓말을 할 수 없는 파티. 다르면 해당 파티는 거짓말을 할 수 있는 파티라서 answer ++.

💡코드

메모리: 14268 KB, 시간: 112 ms

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

class Main {
	static class UnionFind {
		private int[] parents;
		
		UnionFind(int N){
			parents = new int[N];
			makeSet(N);
		}
		
		private void makeSet(int N) {
			for(int i=0; i<N; i++) {
				parents[i] = i;
			}
		}
		
		public int findSet(int x) {
			if(parents[x] != x) {
				parents[x] = findSet(parents[x]);
			}
			return parents[x];
		}
		
		public boolean union(int a, int b) {
			int rootA = findSet(a);
			int rootB = findSet(b);
			if(rootA == rootB) return false;
			else {
				if(rootA < rootB) {
					parents[rootB] = rootA;
				}
				else {
					parents[rootA] = rootB;
				}
			}
			return true;
		}
	}
	
	
	
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken()); int M = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int[] trueGroup = new int[n];
        for(int i=0; i<n; i++) {
        	trueGroup[i] = Integer.parseInt(st.nextToken());
        }
        UnionFind uf = new UnionFind(N+1);
        int answer = 0;
        ArrayList<Integer>[] party = new ArrayList[M];
        int[] firstPeople = new int[M];
        for(int i=0; i<M; i++) {
        	st = new StringTokenizer(br.readLine());
        	int count = Integer.parseInt(st.nextToken());
        	firstPeople[i] = Integer.parseInt(st.nextToken());
        	for(int j=0; j<count-1; j++) {
        		uf.union(firstPeople[i], Integer.parseInt(st.nextToken()));
        	}
        }
        for(int i=0; i<M; i++) {
        	int tmp = uf.findSet(firstPeople[i]);
        	boolean flag = true;
        	for(int j=0; j<n; j++) {
        		if(tmp == uf.findSet(trueGroup[j])) {
        			flag = false; break;
        		}
        	}
        	if(flag) answer ++;
        }
        System.out.println(answer);
    }
}

💡시간복잡도

O(N+Pα(N)+M⋅n)
N: 사람 수

P: 전체 파티 참가자 수 합

M: 파티 수

n: 진실 아는 사람 수

💡개선 코드

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

class Main {
	static class UnionFind {
		private int[] parents;
		
		UnionFind(int N){
			parents = new int[N];
			makeSet(N);
		}
		
		private void makeSet(int N) {
			for(int i=0; i<N; i++) {
				parents[i] = i;
			}
		}
		
		public int findSet(int x) {
			if(parents[x] != x) {
				parents[x] = findSet(parents[x]);
			}
			return parents[x];
		}
		
		public boolean union(int a, int b) {
			int rootA = findSet(a);
			int rootB = findSet(b);
			if(rootA == rootB) return false;
			else {
				if(rootA < rootB) {
					parents[rootB] = rootA;
				}
				else {
					parents[rootA] = rootB;
				}
			}
			return true;
		}
	}
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken()); int M = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        UnionFind uf = new UnionFind(N+1);
        int firstTrue = 0;
        int trueRoot = -1;
        if(n > 0) {
        	firstTrue = Integer.parseInt(st.nextToken());
            for(int i=1; i<n; i++) {
            	uf.union(firstTrue, Integer.parseInt(st.nextToken()));
            }
        }
        int answer = 0;
        int[] firstPeople = new int[M];
        for(int i=0; i<M; i++) {
        	st = new StringTokenizer(br.readLine());
        	int count = Integer.parseInt(st.nextToken());
        	firstPeople[i] = Integer.parseInt(st.nextToken());
        	for(int j=0; j<count-1; j++) {
        		uf.union(firstPeople[i], Integer.parseInt(st.nextToken()));
        	}
        }
        if(n == 0) {System.out.println(M); return;}
        else if(n > 0) trueRoot = uf.findSet(firstTrue);
        for(int i=0; i<M; i++) {
        	int tmp = uf.findSet(firstPeople[i]);
        	if (tmp != trueRoot) answer ++;
        }
        System.out.println(answer);
    }
}

진실을 아는 인원이 0명이면 바로 M 출력하고 종료.
1명 이상이면 진실을 아는 인원 중 1명은 대표로 따로 저장해두고(firstTrue), 진실을 아는 인원들끼리 union 연산을 해서 같은 그룹으로 만들어 둠. 모든 파티 입력이 끝나고 나서, 각 파티에 대표 인원 1명씩 root를 검사해서 firstTrue와 root가 다를 때만 answer++

💡 기억할정보

내가 주로 사용하는 UnionFind는 최적화를 하기 때문에, root가 변경 되는 경우가 잦을 수 있음. 때문에 항상 모든 업데이트가 끝난 직후 findSet을 통해 root를 찾아야 가장 정확함.