1043 - 거짓말 (Java)

 

---

 

문제

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

 

풀이

[* 먼저 말하자면 이 문제는 union - find 로 푸는게 정설인 거 같다.]

 

이 문제의 요점은, 진실을 알고 있는 사람을 통해 건너건너 거짓말쟁이에게 진실이 전해질 수 있다는 점이다.

 

만약 진실을 알고 있는 사람이 1이라고 가정했을 때,

 

파티 1 : 1 2

파티 2 : 2 3

파티 3 : 3 4

 

이런식으로 이루어져 있을 때

 

2번이 1번을 통해 진실을 듣게 된다. 다음에 3번은 2번을 통해 들을 수 있고, 4번은 3번을 통해서 들을 수 있다.  (파티의 순서는 상관없다)

 

따라서 건너건너까지 진실을 알고 있는 사람과의 파티에 엮여있는지 확인할 필요가 있다.

 

나는 스텝을 나눠서 코드를 구현했다.

 

1. 우선 진실을 아는 사람들을 저장한다.

 

2. 같이 파티를 한 사람을 저장한다.

  - 이 때 Map<Integer, List<Integer>> 형태로, Key는 사람번호를 저장하고 리스트에는 같이 파티를 한 사람들을 저장했다.

 

3. 파티를 다시 확인하면서, 2번에서 저장한 자료구조를 활용하여 진실을 아는 사람과 연결되어 있는 사람이 있는지 확인한다.

 

이 스텝으로 문제를 해결했다.

 

결국 건너건너 진실을 아는 사람과 연결되어 있는가? 가 포인트이고, 나는 이 부분을 bfs 를 활용해서 풀었다.

 

 

 

코드

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

public class Main {

    public void solution() throws Exception {
        int answer = 0;
        // 파티에 참가하되, 그 내부에 진실을 아는 사람이 있는지를 판단해야한다.

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        // n : 사람의 수, m : 파티의 수
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        // 진실을 아는 사람은 Set에 저장한다.
        st = new StringTokenizer(br.readLine());
        st.nextToken();

        Set<Integer> truth = new HashSet<>();
        while (st.hasMoreTokens()) {
            truth.add(Integer.parseInt(st.nextToken()));
        }

        // 파티를 List로 입력 받는다.
        List<ArrayList<Integer>> partys = new ArrayList<>();

        for (int i = 0; i < m; i++) {
            ArrayList<Integer> party = new ArrayList<>();
            st = new StringTokenizer(br.readLine());
            st.nextToken();

            while (st.hasMoreTokens()) {
                party.add(Integer.parseInt(st.nextToken()));
            }
            partys.add(party);
        }


        // 파티 구성원을 그래프 형태로 세팅한다.
        Map<Integer, HashSet<Integer>> relationship = new HashMap<>();
        for (int i = 1; i <= n; i++) {
            relationship.put(i, new HashSet<>());
        }

        // O(n) = 250,000
        for (ArrayList<Integer> party : partys) {
            int len = party.size();
            for (int i = 0; i < len - 1; i++) {
                for (int j = i + 1; j < len; j++) {
                    relationship.get(party.get(i)).add(party.get(j));
                    relationship.get(party.get(j)).add(party.get(i));
                }
            }
        }


        // 파티 구성원을 모두 순회하면서 BFS 를 수행하다가 진실을 아는 사람을 만날 경우에는
        for (ArrayList<Integer> party : partys) {

            boolean possible = true;

            // 배열을 돌면서 모두 queue에 넣어주고, 방문 처리를 해준다.
            Deque<Integer> queue = new ArrayDeque<>();
            boolean[] visited = new boolean[n + 1];

            for (Integer i : party) {
                queue.addLast(i);
                visited[i] = true;
            }

            while (!queue.isEmpty()) {
                int target = queue.removeFirst();

                // 만약 진실을 아는 사람이 포함되어 있다면
                if(truth.contains(target)){
                    possible = false;
                    break;
                }

                // target과 연관되어 있는 사람들
                HashSet<Integer> knownPeople = relationship.get(target);

                // 해당 사람이 방문되지 않은 사람이라면, bfs를 수행한다.
                for (Integer knownPerson : knownPeople) {
                    if(!visited[knownPerson]){
                        queue.addLast(knownPerson);
                        visited[knownPerson] = true;
                    }
                }

            }

            if(possible) answer++;
        }

        System.out.println(answer);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}

 

후기

 

제한이 적어서 될 거라 생각했고, 단번에 풀긴했는데.. 정설은 union find 였다. 왜 이생각을 못했을까 ,,