[백준/JAVA] 1043번: 거짓말

🔺 문제

1043번: 거짓말

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int N,M;
    static int[] parent;    // 대표 노드 저장 배열
 
    static int T;           // 진실 아는 사람 수
    static int[] trueP;      // 진실 아는 사람 데이터
 
    static ArrayList<Integer>[] party;    // 파티 데이터
    static int result;
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int N = sc.nextInt();   // 사람 수
        int M = sc.nextInt();   // 파티 수
        
        int T = sc.nextInt();
        result = 0;
        
        // 진실 아는 사람
        trueP = new int[T];
        for(int i = 0 ; i < T ; i++) {
            trueP[i] = sc.nextInt();
        }
        
        // 파티 데이터 저장
        party = new ArrayList[M];
        for(int i = 0 ; i < M ; i++) {
            party[i] = new ArrayList<Integer>();
 
            int party_size = sc.nextInt();
            for(int j = 0 ; j < party_size ; j++) {
                party[i].add(sc.nextInt());
            }
        }
         
        // 배열 초기화
        parent = new int[N + 1];
        for(int i = 1 ; i <= N ; i++) {
            parent[i] = i;
        }
        
        // 각 파티에 참여한 사람 한 그룹으로 만들기
        for(int i = 0 ; i < M ; i++) {
            int firstPeople = party[i].get(0);    // i번째 파티의 첫 번째 사람
 
            for(int j = 1 ; j < party[i].size() ; j++) {
                union(firstPeople, party[i].get(j));
            }
        }
        
        // 각 파티의 대표 노드와 진실을 아는 사람들의 대표 노드가 같다면 과장 X
        for(int i = 0 ; i < M ; i++) {
            boolean isPossible = true;
            int cur = party[i].get(0);
 
            for(int j = 0 ; j < trueP.length ; j++) {
                if(find(cur) == find(trueP[j])) {
                    isPossible = false;
                    break;
                }
            }
            // 모두 다르면 결과값 1 증가
            if(isPossible)  result++;
        }
        
        System.out.println(result);
    }
    
    
    public static void union(int a, int b) {
        a = find(a);
        b = find(b);
        
        if(a != b) parent[b] = a;
    }
    public static int find(int a) {
        if(a == parent[a]) return a;
        return parent[a] = find(parent[a]);
    }
}

✅ 해결 아이디어
✔ 유니온 파인드
- ArrayList를 담고 있는 1차원 배열 사용 (ArrayList<Integer>[])

 

---

🔺 다른 풀이들

- 복습용

[백준] 1043 : 거짓말 (JAVA/자바)

[백준/boj] 1043: 거짓말 (Java) / Union-Find

 

 

- DFS 사용하심 (개쩜;;)

[백준] 1043번: 거짓말 - JAVA

 

 

- BFS 사용하심

[백준 1043 - Java] 거짓말

[백준 1043] 거짓말 - JAVA //le_effort

---

💬 느낀 점

코드가 길어지고 그럴수록 머릿속에서만 생각해서 바로 할 수 없으니까

꼭 손으로 수도코드 작성하고 순서를 작성하는 게 필요하단 생각이 들었다.

 

 

1회독	2회독	3회독	4회독	5회독
V	6/22

 

 

(+ 6/22 2회독)

마지막에 "각 파티의 대표노드 vs 진실을 아는 사람들의 대표 노드" 이 부분

어찌할까 생각하다가 타임아웃..

import java.util.*;
import java.io.*;
 
public class Main {
    static int[] parent;
    
    static int trueNum;     // 진실 아는 사람 수
    static int[] trueArr;   // 진실 아는 사람 배열
    
    static ArrayList<Integer>[] party;  // 파티 데이터
    static int cnt;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Scanner sc = new Scanner(System.in);
        
        int N = sc.nextInt();   // 사람 수
        int M = sc.nextInt();   // 파티 수
        
        cnt = 0;
        
        // 진실 아는 사람 수, 번호 입력 받기
        trueNum = sc.nextInt(); // 진실 아는 사람 수
        trueArr = new int[trueNum];
        for(int i = 0 ; i < trueNum ; i++) {
            trueArr[i] = sc.nextInt();
        }
        
        // 부모 배열 초기화
        parent = new int[N + 1];
        for(int i = 1 ; i <= N ; i++) {
            parent[i] = i;
        }
        
        // 각 파티마다 오는 사람 수 , 번호 입력 받기
        party = new ArrayList[M];
        for(int i = 0 ; i < M ; i++) {
            party[i] = new ArrayList<Integer>();
            
            int party_size = sc.nextInt();
            for(int j = 0 ; j < party_size ; j++) {
                party[i].add(sc.nextInt());
            }
        }
        
        // 인접 리스트 각 원소에 대해 union 수행 (= 각 파티에 참여한 사람 한 그룹으로 만들기)
        for(int i = 0 ; i < M ; i++) {
            int first = party[i].get(0);
            
            for(int j = 1 ; j < party[i].size() ; j++) {
                union(first, party[i].get(j));
            }
        }
        
        // 각 파티의 대표노드 vs 진실을 아는 사람들의 대표 노드
        for(int i = 0 ; i < M ; i++) {
            boolean isPossible = true;
            int cur = party[i].get(0);  // 각 파티의 대표 노드
            
            for(int j = 0 ; j < trueArr.length ; j++) {
                if(find(cur) == find(trueArr[j])) {
                    isPossible = false;
                    break;
                }
            }
            
            if(isPossible) cnt++;
        }
        
        System.out.println(cnt);
    }
    
    static void union(int a, int b) {
        a = find(a);
        b = find(b);
        
        if(a != b) parent[b] = a;
    }
    static int find(int a) {
        if(a == parent[a])  return a;
        return parent[a] = find(parent[a]);
    }
}
 

 

---

(참고)

✔ Do it 알고리즘 코딩테스트 자바편