[백준 - 1043] 거짓말 - Java

문제 설명

 

1043번: 거짓말

 

풀이 회고

문제 이해하기

해당 문제는 '문제를 이해'하는데 많은 시간이 소요되었습니다. 😥 우선 문제에서 요구하는 것은 지민이가 과장된 이야기를 할 수 있는 파티의 수 즉, 진실을 아는 사람이 포함되어 있지 않는 파티의 수를 구하는 것입니다. 이때 중요한 점(놓치기 쉬운 점)은 최초 진실을 아는 사람이 포함되어 있는 파티에 다른 사람(최초 진실 구별 X)이 최초 진실을 아는 사람이 없는 다른 파티에 있더라도 지민이는 앞서 최초 진실을 아는 사람이 존재하기 때문에 어쩔 수 없이 해당 사람에게 진실된 이야기를 말했기 때문에 다른 파티에서 이 사람을 보더라도 과장을 못한다는 점입니다.

 

해당 문제 설명의 첫 줄에 이러한 문장이 있습니다. "~ 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, ~" 즉, 문제를 제대로 이해하는데 시간을 오래 허비한 이유는 문제를 제대로 읽지 않고(흘려 읽었음) 지민이가 각각의 파티에서 '다른 이야기'를 할 것이라는 편견이 있었기 때문이었습니다.

 

접근 방법

우선 진실을 판별할 수 있는 사람들을 입력받을 때는 자료구조로 요소의 중복을 허용하지 않는 HashSet을 이용했습니다. 이는 추후에 특정 파티에서 과장을 할 수 있는지 여부를 판단할 때 사용하기 위함인데, 진실을 판별할 수 있는 사람이 해당 파티에 한 명이라도 존재하는지 여부를 확인하는 것입니다. 따라서 진실을 판별할 수 있는 사람이 중복되서 들어갈 필요가 없습니다.

 

        // 진실을 판별할 수 있는 사람들 입력
        st = new StringTokenizer(br.readLine());
        int countOfTruthfulPerson = Integer.parseInt(st.nextToken());

        if (countOfTruthfulPerson == 0) {
            System.out.println(m);
            return;
        }

        Set<Integer> truthfulPerson = new HashSet<>();

        for (int i = 0; i < countOfTruthfulPerson; i++) {
            truthfulPerson.add(Integer.parseInt(st.nextToken()));
        }

 

이후 파티에 참석하는 사람들을 입력받을 때는 별도 Party 구조체를 선언하여 파티에 참석하는 사람들을 저장하는 ArrayList 자료구조와 과장된 이야기를 할 수 있는지 여부에 대한 boolean 값을 멤버(최초 true)로 두었습니다. 이 역시 추후에 특정 파티에서 과장을 할 수 있는지 여부를 판단할 때 사용하기 위함이었습니다. 사실 이를 별도의 구조체가 아닌 HashMap으로 구현하고자 했으나, HashMap의 경우 중복된 키 값을 허용하지 않기 때문에 사용할 수 없었습니다. 예를 들어 HashMap의 키 값을 ArrayList로 둔다면 어떤 파티에 참석하는 사람이 1번 1명이고 또 다른 파티에 참석하는 사람이 동일하게 1번 1명이라면 다른 주소의 ArrayList라고 할지라도 내부 요소가 같기 때문에 HashMap에서는 이를 중복이라고 판단합니다. boolean을 키 값으로 두는 것은 말할 것도 없습니다.

 

    static class Party {

        List<Integer> person;
        boolean exaggerationIsPossible;

        public Party(List<Integer> person, boolean exaggerationIsPossible) {
            this.person = person;
            this.exaggerationIsPossible = exaggerationIsPossible;
        }

        public boolean contains(int human) {
            return this.person.contains(human);
        }
    }
    
    // (...생략...)

        // 파티에 참석하는 사람들 입력
        List<Party> parties = new ArrayList<>();

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

            for (int j = 0; j < countOfPersonInParty; j++) {
                personInParty.add(Integer.parseInt(st.nextToken()));
            }

            parties.add(new Party(personInParty, true));
        }

 

이제 주어진 (최초의) 진실을 판별할 수 있는 사람들을 통해 주어진 파티들에서 지민이가 과장된 이야기를 할 수 없는 파티를 체크(check)하고 해당 파티에 포함된 사람들을 다시 진실을 판별할 수 있는 사람들로 분류(Queue에 추가)하여 다시 주어진 파티들을 탐색했습니다. 이 과정에서 진실을 판별할 수 있는 사람으로 모든 탐색을 마친 경우에는 이후에 한 번 더 탐색할 필요가 없으므로 해당 사람은 Queue에서 제외시켰습니다.

 

        // 진실을 판별할 수 있는 사람들 추가 및 진실을 말 할 수 없는 파티 체크(check)
        Set<Integer> tempSet = new HashSet<>(truthfulPerson);
        Queue<Integer> truthfulPersonQueue = new LinkedList<>(tempSet);

        while (!truthfulPersonQueue.isEmpty()) {

            int tp = truthfulPersonQueue.poll();

            for (Party party : parties) {
                if (party.exaggerationIsPossible && party.contains(tp)) {
                    party.exaggerationIsPossible = false;
                    for (int p : party.person) {
                        truthfulPerson.add(p);
                        tempSet.add(p);
                    }
                }
            }

            tempSet.remove(tp);
            truthfulPersonQueue = new LinkedList<>(tempSet);
        }

 

이러한 방법으로 모든 탐색을 마치면 주어진 파티별로 최초에 true로 초기화 됐었던 과장 가능 여부가 그대로 true인 Party 객체의 개수 즉, 문제에서 요구하는 지민이가 과장된 이야기를 할 수 있는 파티의 수를 구할 수 있습니다.

 

        // 결과값 출력
        for (Party party : parties) {
            if (party.exaggerationIsPossible) result++;
        }

 

 

전체 소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Set;
import java.util.StringTokenizer;

class Main {

    static class Party {

        List<Integer> person;
        boolean exaggerationIsPossible;

        public Party(List<Integer> person, boolean exaggerationIsPossible) {
            this.person = person;
            this.exaggerationIsPossible = exaggerationIsPossible;
        }

        public boolean contains(int human) {
            return this.person.contains(human);
        }
    }

    public static void main(String[] args) throws IOException {

        int result = 0;

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

        int n, m;
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        // 진실을 판별할 수 있는 사람들 입력
        st = new StringTokenizer(br.readLine());
        int countOfTruthfulPerson = Integer.parseInt(st.nextToken());

        if (countOfTruthfulPerson == 0) {
            System.out.println(m);
            return;
        }

        Set<Integer> truthfulPerson = new HashSet<>();

        for (int i = 0; i < countOfTruthfulPerson; i++) {
            truthfulPerson.add(Integer.parseInt(st.nextToken()));
        }

        // 파티에 참석하는 사람들 입력
        List<Party> parties = new ArrayList<>();
        
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int countOfPersonInParty = Integer.parseInt(st.nextToken());
            List<Integer> personInParty = new ArrayList<>();

            for (int j = 0; j < countOfPersonInParty; j++) {
                personInParty.add(Integer.parseInt(st.nextToken()));
            }

            parties.add(new Party(personInParty, true));
        }

        // 진실을 판별할 수 있는 사람들 추가 및 진실을 말 할 수 없는 파티 체크(check)
        Set<Integer> tempSet = new HashSet<>(truthfulPerson);
        Queue<Integer> truthfulPersonQueue = new LinkedList<>(tempSet);

        while (!truthfulPersonQueue.isEmpty()) {

            int tp = truthfulPersonQueue.poll();

            for (Party party : parties) {
                if (party.exaggerationIsPossible && party.contains(tp)) {
                    party.exaggerationIsPossible = false;
                    for (int p : party.person) {
                        truthfulPerson.add(p);
                        tempSet.add(p);
                    }
                }
            }

            tempSet.remove(tp);
            truthfulPersonQueue = new LinkedList<>(tempSet);
        }

        // 결과값 출력
        for (Party party : parties) {
            if (party.exaggerationIsPossible) result++;
        }

        System.out.println(result);
    }
}

 

 

참고자료

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