[백준 1043] 거짓말 (JAVA)

백준 1043번 문제 - 거짓말

1043번: 거짓말

---

문제 분석

 

 

• N,M 입력 : 지민이는 N명의 친구가 있으며, M개의 파티에 참여해야한다.
• 수 K와 K명의 진실을 아는 사람 입력
• M개의 파티를 입력
  - 수 K와 K명의 파티에 참여하는 사람 입력 (M개의 파티에 순서는 없다)
• 진실을 아는 사람이 있을 때에는 과장해서 이야기 할 수 없을 때, M개의 파티에서 과장해서 이야기할 수 있는 파티의 개수를 출력해라.
  + 진실을 아는 사람과 함께 파티를 보낸 사람 또한 진실을 아는 사람이 된다.

 

---

해결 키 포인트

 

• 유니온 파인드(union-find) 개념 사용
• 진실을 아는 사람들은 -1 집합으로 한다.
  • 2번째줄 입력으로 주어지는 진실을 아는 사람들은 -1 집합으로
  • M개의 파티를 할 때, 같은 파티를 하는 사람들을 같은 집합으로 설정 ( 유니온 이용 )
    - 이때 만약 같은 집합에 -1 집합 사람이 있을 경우, 해당 파티 집합은 -1 집합으로 설정
• M개의 파티를 또 다른 변수로 저장해놓고, 파티 집합 설정 → 파티 검사 ( 과장해서 말할 수 있는지 검사 )

 

• 필자는 처음에 진실을 아는 사람은 -1 집합이기 때문에 union 설정을 따로 안하고,
  같은 파티에 -1인 사람이 있을 경우 해당 파티 파티원들을 모두 -1 집합으로 변형하는 방식으로 했다
  • 이렇게하니, 문제가 된 부분은 진실을 아는 사람이 1일때 위에서 아래로 파티를 확인할 때,
    위에 파티 파티원은 2,3 이고, 다음 파티 파티원이 1, 2 일 때
    ➡️ 위에 파티원은 과장해서 말해도 되는 파티가 되서 문제와 조건이 맞지 않아진다.

---

유니온 파인트 (union-find)

여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union 연산과 두 노드가 같은 집합에 속해 있는지 확인하는 find 연산으로 구성되어 있는 알고리즘이다.

 

• union 연산 : 각 노드가 속한 집합을 1개로 합치는 연산이다. 노드 a, b가 a ∈ A, b ∈ B일 때 union(a, b)는 A∪B를 말한다.
• find 연산 : 특정 노드 a에 관해 a가 속한 집합의 대표 노드를 반환하는 연산이다. 노드 a, b가 a ∈ A일 때 find(a)는 A 집합의 대표 노드를 반환한다. 

 

Union 연산 알고리즘

• 1차원 배열을 이용해서, i번째 값은 i로 변수 초기화한다. ( 대표 노드는 본인 )
• union(a, b) 연산은 a와 b의 대표 노드를 알아내 'b 대표 노드'의 value( list['b 대표 노드'] )을 'a 대표 노드'로 변경한다.
  • index == list[index] : 해당 index가 집합의 대표 노드
    index !=  list[index] : 대표 노드를 알아내야 함 ( 배열의 list[index]와 list[list[index]] 비교 )
  • list['b 대표 노드'] = 'a 대표 노드' 로 b 집합을 a 집합에 포함시킨다.

 

Find 연산 알고리즘

• 대상 노드 배열에 index 값과 value 값이 동일한지 확인
• 동일하지 않으면 value 값이 가리키는 index 위치로 이동
• 이동 위치의 index 값과 value 값이 같을 때까지 앞 방법들을 반복 (재귀함수로)
• 대표 노드에 도달하면 재귀함수를 빠져나오면서 거치는 모든 노드 값을 대표 노드 값으로 변경

---

코드

 

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

public class Main {
    public static int [] collection;
    public static void main(String [] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // N,M 입력
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        // 모든 사람 각 집합으로 생성
        collection = new int[N+1];
        for(int i=0;i<=N;i++) {
            collection[i] = i;
        }

        // 진실을 아는 사람 k명 주어지기 - 진실을 아는 경우 -1 집합으로 설정
        st = new StringTokenizer(br.readLine());
        int K = Integer.parseInt(st.nextToken());
        for(int i=0;i<K;i++) {
            int person = Integer.parseInt(st.nextToken());

            collection[person] = -1;
        }

        // M개의 파티의 참여하는 사람을 arraylist로 설정
        ArrayList<Integer> [] parties = new ArrayList[M];

        // M개의 파티 입력
        for(int i=0;i<M;i++) {
            parties[i] = new ArrayList<>();
            ArrayList<Integer> party = parties[i];

            // 파티에 참여하는 사람 k명 입력
            st = new StringTokenizer(br.readLine());
            K = Integer.parseInt(st.nextToken());
            for(int j=0;j<K;j++) {
                int person = Integer.parseInt(st.nextToken());

                if(!party.isEmpty()) {
                    // party에 있는 사람과 동일 집합으로 설정
                    union(party.get(j -1), person);
                }

                // i번째 파티 참여하는 사람으로 추가
                party.add(person);
            }
        }

        // 과장해서 말할 수 있는 파티 개수
        int count = 0;

        // 모든 파티에서 진실을 아는집합이 없을 경우(-1 집합이 없을 경우)에만 count 증가
        for(int i=0;i<parties.length;i++) {
            ArrayList<Integer> party = parties[i];

            // 진실을 아는지 확인 변수
            boolean isTrust = false;

            // 파티 참여인들을 확인하면서 -1 집합인 사람이 있을 경우 isTrust 변경 후 종료
            for(int j=0;j<party.size();j++) {
                if(find(party.get(j)) == -1) {
                    isTrust = true;
                    break;
                }
            }

            // 진실을 아는 사람이 없을 경우만 count 증가
            if(!isTrust) {
                count++;
            }
        }

        // 과장할 수 있는 횟수 출력
        bw.write(count+"\n");
        bw.flush();
        bw.close();
    }

    public static void union(int a, int b) {
        int mainA = a, mainB = b;
        if(a != collection[a]) {
            if(collection[a] == -1) mainA = -1;
            else mainA = find(a);
        }
        if(b != collection[b]) {
            if(collection[b] == -1) mainB = -1;
            else mainB = find(b);
        }

        if(mainB == -1) {
            if(mainA != -1)
                collection[mainA] = -1;
        }
        else {
            collection[mainB] = mainA;
        }
    }

    public static int find(int a) {
        // 자신이 대표 노드이거나, 자신의 집합이 -1 집합으로 진실을 아는 집합일 경우 return
        if(a == collection[a] || collection[a] == -1)
            return collection[a];

        // 그게 아니면 노드의 값으로 다시 대표노드를 찾아 변경 후 리턴
        collection[a] = find(collection[a]);
        return collection[a];
    }
}