문제 링크

문제 간단 해석

진실을 아무도 접할 수 없는 파티에 가서 거짓말을 하는 문제.

Java

오늘은 여타 알고리즘 문제 풀듯, 메서드별로 쪼개지 않고 그냥 작성했다.

풀이 코드

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

public class b1043 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        int knowTruthNum = Integer.parseInt(st.nextToken());
        Set<Integer> knowTruthPeople = new HashSet<>();

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

        Map<Integer, Set<Integer>> peopleAndParty = new HashMap<>();
        Map<Integer, Set<Integer>> partyAndPeople = new HashMap<>();

        for (int party = 0; party < M; party++) {
            st = new StringTokenizer(br.readLine());
            int numberOfPeopleAtTheParty = Integer.parseInt(st.nextToken());
            Set<Integer> partyPeople = new HashSet<>();

            for (int i = 0; i < numberOfPeopleAtTheParty; i++) {
                int people = Integer.parseInt(st.nextToken());
                partyPeople.add(people);
                Set<Integer> partyIAmIn = peopleAndParty.getOrDefault(people, new HashSet<>());
                partyIAmIn.add(party);
                peopleAndParty.put(people, partyIAmIn);
            }

            partyAndPeople.put(party, partyPeople);
        }

        Deque<Integer> deque = new ArrayDeque<>(knowTruthPeople);
        Set<Integer> avoidParty = new HashSet<>();

        while (!deque.isEmpty()) {
            int knowTrueMan = deque.removeFirst();

            for (int party : peopleAndParty.getOrDefault(knowTrueMan, new HashSet<>())) {
                if (avoidParty.contains(party)) {
                    continue;
                }

                avoidParty.add(party);

                for (int people : partyAndPeople.getOrDefault(party, new HashSet<>())) {
                    if (!knowTruthPeople.contains(people)) {
                        knowTruthPeople.add(people);
                        deque.addLast(people);
                    }
                }
            }
        }

        System.out.println(partyAndPeople.size() - avoidParty.size());
    }
}

해석

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

st = new StringTokenizer(br.readLine());
int knowTruthNum = Integer.parseInt(st.nextToken());
Set<Integer> knowTruthPeople = new HashSet<>();

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

Map<Integer, Set<Integer>> peopleAndParty = new HashMap<>();
Map<Integer, Set<Integer>> partyAndPeople = new HashMap<>();

Scanner보다 빠른 BufferdReader와 StringTokenizer의 조합을 사용하였다.
처음엔 Scanner를 사용했는데, 속도 차이가 의외로 큰 걸 알 수 있었다.

진실을 알고 있는 사람들을 Set에 넣어주고, 사람-파티와 파티-사람관계를 맺기 위한 Map을 두 개 선언했다. 이차원 배열로 해도 되지만, 만약 사람과 파티의 최대 범위가 증가한다면 해당 자료형이 더 효율적이지 않을까 생각했다.

for (int party = 0; party < M; party++) {
    st = new StringTokenizer(br.readLine());
    int numberOfPeopleAtTheParty = Integer.parseInt(st.nextToken());
    Set<Integer> partyPeople = new HashSet<>();

    for (int i = 0; i < numberOfPeopleAtTheParty; i++) {
        int people = Integer.parseInt(st.nextToken());
        partyPeople.add(people);
        Set<Integer> partyIAmIn = peopleAndParty.getOrDefault(people, new HashSet<>());
        partyIAmIn.add(party);
        peopleAndParty.put(people, partyIAmIn);
    }

    partyAndPeople.put(party, partyPeople);
}

파티에 참여하는 사람들로 사람-파티를 작성하고, 최종적으로 파티-사람을 작성했다.

Deque<Integer> deque = new ArrayDeque<>(knowTruthPeople);
Set<Integer> avoidParty = new HashSet<>();

while (!deque.isEmpty()) {
    int knowTrueMan = deque.removeFirst();

    for (int party : peopleAndParty.getOrDefault(knowTrueMan, new HashSet<>())) {
        if (avoidParty.contains(party)) {
            continue;
        }

        avoidParty.add(party);

        for (int people : partyAndPeople.getOrDefault(party, new HashSet<>())) {
            if (!knowTruthPeople.contains(people)) {
                knowTruthPeople.add(people);
                deque.addLast(people);
            }
        }
    }
}

System.out.println(partyAndPeople.size() - avoidParty.size());

진실을 알고 있던 사람들을 deque에 넣는다. 또한 피해야 할 파티 목록(거짓말이 들통날 파티 목록)을 Set으로 작성한다.

진실을 아는 사람을 deque의 앞쪽에서 하나씩 가져온다. 해당 인원이 참여한 파티는 진실이 퍼지기에 거짓말을 피해야만 한다.
해당 인원이 참여한 파티 목록을 가져와 순회하는데, 이미 내가 피하기로 마음먹은 파티라면 넘어간다.
그렇지 않은 파티라면 목록에 넣고, 해당 파티에 참여하는 사람들을 확인한다. 모두 진실을 듣게 될 것이므로, 진실을 알고 있던 사람들 목록에 없다면 넣어준 후 deque에 추가시킨다.

모든 파티 길이(M)에서 내가 피해야 할 파티 목록의 수만큼을 빼면 된다. M의 존재를 깜빡 잊고 partyAndPeople.size()를 썼는데 뭐 같은 값이니까..

여담

BufferdReader와 StringTokenizer의 존재, 그리고 백준에 Java를 제출하는 법에 대해 배웠다.
앞으로는 주 언어를 Java로 설정하려 하기에, 알고리즘 문제도 풀고 공부도 하며 열심히 해볼 생각.