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

목차

• 문제
• 내가 푼 방법
• 자바 코드
• 결과 및 회고

---

1. 문제

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

---

2. 내가 푼 방법

핵심은 각 파티마다 참석한 사람들을 union-find를 이용해 같은 부모를 가지는 방법으로 연결시켜 준다.

그 후에 진실을 아는 사람들의 부모를 true로 변경해 줌으로써 문제를 풀 수 있다.

 

union-find 알고리즘은 두 정점이 같은 그래프에 속하는지 확인할 수 있는 알고리즘이다. 아래의 find 함수와 union 함수를 사용해 구현할 수 있는데, find함수는 입력받은 x의 부모를 찾는 함수이고 union 함수는 입력받은 a와 b가 같은 부모를 가진다는 설정해 주는 함수이다.

parent 배열의 초기값으로 자기 자신을 부모로 가지기 때문에. 두 정점이 같은 그래프에 속하는지 확인할 수 있는 방법은 find로 찾은 부모 값이 같다면 같은 그래프, 다르다면 다른 그래프에 속하는 것을 알 수 있다.

 

이제 우리는 각각의 파티에 속한 사람들이 같은 부모를 가지게 됨을 깨달을 수 있다.

// party 초기화
for (int m = 0; m < M; m++) {
    st = new StringTokenizer(br.readLine());
    int human = Integer.parseInt(st.nextToken());

    int a = Integer.parseInt(st.nextToken());
    party[m] = new ArrayList<>();
    party[m].add(a);

    for (int i = 1; i < human; i++) {
        int b = Integer.parseInt(st.nextToken());

        party[m].add(b);
        union(parent, a, b);
        a = b;
    }
}

 

그 후 진실을 아는 사람들을 추가해주고, 파티를 돌면서 참석한 한 사람의 부모를 확인하면 result를 증가시킬 수 있다. (각 파티 참석 인원이 동일한 부모를 가지므로 한 명만 확인하면 됨.)

// know 추가
for (int i = 1; i <= N; i++) {
    if (know[i]) {
    know[find(parent, i)] = true;
    }
}

int result = 0;
for (List<Integer> p : party) {
    if (!know[find(parent, p.get(0))]) result++;
}

bw.write(result+"");

---

3. 자바 코드

깃허브 풀이 주소

https://github.com/geujeog/BOJ/blob/main/B1043.java

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

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

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

        int[] parent = new int[N+1];
        boolean[] know = new boolean[N+1];
        List<Integer>[] party = new List[M];

        for (int i = 1; i <= N; i++) {
            parent[i] = i;
        }

        for (int i = 0; i < M; i++) {
            party[i] = new ArrayList<>();
        }

        st = new StringTokenizer(br.readLine());
        int knowPeople = Integer.parseInt(st.nextToken());
        for (int i = 0; i < knowPeople; i++) {
            know[Integer.parseInt(st.nextToken())] = true;
        }

        for (int m = 0; m < M; m++) {
            st = new StringTokenizer(br.readLine());
            int human = Integer.parseInt(st.nextToken());

            int a = Integer.parseInt(st.nextToken());
            party[m].add(a);

            for (int i = 1; i < human; i++) {
                int b = Integer.parseInt(st.nextToken());

                party[m].add(b);
                union(parent, a, b);
                a = b;
            }
        }

        for (int i = 1; i <= N; i++) {
            if (know[i]) {
                know[find(parent, i)] = true;
            }
        }

        int result = 0;
        for (List<Integer> p : party) {
            if (!know[find(parent, p.get(0))]) result++;
        }

        bw.write(result+"");

        br.close();
        bw.flush();
        bw.close();
    }

    public static void union (int[] parent, int a, int b) {
        a = find(parent, a);
        b = find(parent, b);

        if (a != b) {
            if (a < b) parent[b] = a;
            else parent[a] = b;
        }
    }

    public static int find (int[] parent, int x) {
        if (parent[x] == x) return x;
        return find(parent, parent[x]);
    }
}

---

4. 결과 및 회고

union-find 알고리즘에 대해서 잘 응용하게 된 문제였던 것 같다.