[백준] 1043 - 거짓말 (JAVA)

https://www.acmicpc.net/problem/1043
keyword : Queue, 그래프, BFS

문제

지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 과장해서 말한다. 당연히 과장해서 이야기하는 것이 훨씬 더 재미있기 때문에, 되도록이면 과장해서 이야기하려고 한다. 하지만, 지민이는 거짓말쟁이로 알려지기는 싫어한다. 문제는 몇몇 사람들은 그 이야기의 진실을 안다는 것이다. 따라서 이런 사람들이 파티에 왔을 때는, 지민이는 진실을 이야기할 수 밖에 없다. 당연히, 어떤 사람이 어떤 파티에서는 진실을 듣고, 또다른 파티에서는 과장된 이야기를 들었을 때도 지민이는 거짓말쟁이로 알려지게 된다. 지민이는 이런 일을 모두 피해야 한다.

사람의 수 N이 주어진다. 그리고 그 이야기의 진실을 아는 사람이 주어진다. 그리고 각 파티에 오는 사람들의 번호가 주어진다. 지민이는 모든 파티에 참가해야 한다. 이때, 지민이가 거짓말쟁이로 알려지지 않으면서, 과장된 이야기를 할 수 있는 파티 개수의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 사람의 수 N과 파티의 수 M이 주어진다.

둘째 줄에는 이야기의 진실을 아는 사람의 수와 번호가 주어진다. 진실을 아는 사람의 수가 먼저 주어지고 그 개수만큼 사람들의 번호가 주어진다. 사람들의 번호는 1부터 N까지의 수로 주어진다.

셋째 줄부터 M개의 줄에는 각 파티마다 오는 사람의 수와 번호가 같은 방식으로 주어진다.

N, M은 50 이하의 자연수이고, 진실을 아는 사람의 수는 0 이상 50 이하의 정수, 각 파티마다 오는 사람의 수는 1 이상 50 이하의 정수이다.

출력

첫째 줄에 문제의 정답을 출력한다.

 

---

 

풀이

쉽게 눈에 들어오지는 않지만, 이 문제는 그래프 탐색문제이다. 노드를 파티에 참석하는 사람들, 간선은 파티라고 생각하면, 일반적인 그래프 문제로 생각할 수 있지 않겠는가?

나는 큐와 HashSet을 이용하여 해결했지만, 이 풀이를 쓰면서 이 문제가 그래프 탐색 문제였다는 생각이 들었다.

내가 짠 이 코드도 로직이 BFS와 비슷하게 돌아가기도 하고 문제의 알고리즘 분류가 그래프 탐색이라고 되어 있는 것을 보면, 아마... 맞지 않을까?

어쨋든, 이 문제의 핵심은 큐를 이용하는 것이다. 큐에 사람을 차례대로 추가하며 탐색하다는 아이디어만 떠올릴 수 있었다면 쉽게 해결할 수 있을 거라고 생각한다.

나는 아래와 같이 로직을 구성했다.

1. 진실을 알고 있는 사람을 우선하여 어떤 파티에 참석하는지 탐색
   • 이 과정에서 큐를 사용한다.
   • 이 사람과 같이 파티에 참석한 사람은 큐에 추가
   • 이 사람이 참석한 파티는 다음부터 탐색 대상에서 제외한다.
2. 큐가 비면 탐색을 종료한다.
   • 문제의 해는 탐색의 대상이 되지 않은 파티의 수가 된다.

이 과정에서 파티에 참석하는 인원 중, 진실을 아는 사람이 존재하는지를 빠르게 탐색하기 위해 HsahSet을 이용했다. HashSet의 탐색 시간 복잡도는 $O(1)$이다.

하지만 문제에서 주어지는 사람의 수(N)와 파티의 수(M)의 범위가 50 이하이기 때문에 굳이 HashSet을 쓰지 않고 배열이나 리스트를 사용하여 완전탐색을 진행해도 시간 초과가 나지 않을 것 같기는 하다. 물론, 굳이 효율성을 낮출 필요는 없으니 배열을 활용하더라도 이분탐색을 이용하는 것이 좋겠지만 말이다.

이 정도만 고려해서 코드를 구현하면 된다.

 

풀이

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

public class Main {  
    private static Queue<Integer> knownPeopleQueue;  
    private static ArrayList<HashSet<Integer>> parties;
    private static boolean[] canLie; // 어떤 파티에서 거짓말을 할 수 있는지 저장  
    private static boolean[] checked; // 진실을 아는 사람 중, 확인을 했는지 여부  

    private static int n, m;  
    public static void main(String[] args) throws IOException {  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
        StringTokenizer stk = new StringTokenizer(br.readLine());  

        n = Integer.parseInt(stk.nextToken());  
        m = Integer.parseInt(stk.nextToken());  

        knownPeopleQueue = new LinkedList<>();  
        parties = new ArrayList<>();  

        canLie = new boolean[m];  
        checked = new boolean[n + 1];  

        Arrays.fill(canLie, true);  
        Arrays.fill(checked, false);  

        stk = new StringTokenizer(br.readLine());  
        int truthCnt = Integer.parseInt(stk.nextToken());  
        for (int i = 0; i < truthCnt; i++) {  
            int tmp = Integer.parseInt(stk.nextToken());  
            knownPeopleQueue.add(tmp);  
            checked[tmp] = true;  
        }  

        for (int i = 0; i < m; i++) {  
            stk = new StringTokenizer(br.readLine());  
            int tmp = Integer.parseInt(stk.nextToken());  

            parties.add(new HashSet<>());  
            for (int j = 0; j < tmp; j++) {  
                parties.get(i).add(Integer.parseInt(stk.nextToken()));  
            }  
        }  


        System.out.println(solution());  
    }

     private static int solution() {  
        int lyingPartyCount = m;  

        while (!knownPeopleQueue.isEmpty()) {  
            int knownPerson = knownPeopleQueue.poll();  

            for (int i = 0; i < m; i++) {  
                HashSet<Integer> party = parties.get(i);  

                if (party.contains(knownPerson)) { // 진실을 아는 사람이 파티에 참여했다면  
                    if (canLie[i]) { // 거짓말을 할 수 있을 줄 알았다면  
                        canLie[i] = false;  
                        lyingPartyCount--;  

                        for (Integer person : party) {  
                            if(!checked[person]) {  
                                checked[person] = true;  
                                knownPeopleQueue.add(person);  
                            }  
                        }  
                    }  
                }  
            }  

            if(lyingPartyCount == 0) {  
                break;  
            }  
        }  

        return lyingPartyCount;  
    }  
}

 

---

 

문제를 풀고 다른 분들의 풀이를 찾아봤는데, 대부분 유니온 파인드 알고리즘을 사용하여 풀이한 것을 보았다. 이전에 공부했던 기억은 있는데, 다시 보니 이해가 잘 안 가서 공부를 다시 해야할 듯하다.