[백준 JAVA] 1043번: 거짓말

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

 

처음 풀이

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

public class Main {
    static int N, M, count;
    static int[] truth;
    static int[][] graph;
    static List<Integer>[] party;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        truth = new int[N + 1];
        graph = new int[N + 1][N + 1];

        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        for (int i = 0; i < n; i++) {
            truth[Integer.parseInt(st.nextToken())] = 1;
        }

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

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int m = Integer.parseInt(st.nextToken());
            for (int j = 0; j < m; j++) {
                party[i].add(Integer.parseInt(st.nextToken()));
            }
            for (int j = 0; j < m; j++) {
                int cur = party[i].get(j);
                for (int k = 0; k < m; k++) {
                    graph[cur][party[i].get(k)] = 1;
                }
            }
        }

        Queue<Integer> q = new ArrayDeque<>();
        for (int i = 1; i <= N; i++) {
            if (truth[i] == 1) q.offer(i);
        }
        while (!q.isEmpty()) {
            int cur = q.poll();
            for (int i = 1; i <= N; i++) {
                if (graph[cur][i] == 1 && truth[i] == 0) {
                    truth[i] = 1;
                    q.offer(i);
                }
            }
        }
        for (int i = 0; i < M; i++) {
            boolean canLie = true;
            for (int id : party[i]) {
                if (truth[id] == 1) {
                    canLie = false;
                    break;
                }
            }
            if (canLie) count++;
        }

        System.out.println(count);
    }
}

 

거짓말 문제를 처음 풀 때 BFS로 접근해서 풀긴 했지만, 코드가 조금 무거워지고 구현이 돌아가는 느낌이 들었다. 문제를 다시 정리해보니 이 문제는 단순 그래프 문제가 아니라 “전파” 문제에 가깝다는 걸 느꼈다.

핵심은 진실이 어떻게 퍼지는지 이해하는 것이다.

진실을 아는 사람이 어떤 파티에 참여하면 그 파티에 있는 사람들은 모두 진실을 알게 된다. 그리고 그 사람이 다른 파티에 참여하면 또 그 파티로 진실이 퍼진다. 이 과정이 반복되면서 결국 진실은 연결된 모든 사람에게 전파된다.

예를 들어 이런 경우를 생각해볼 수 있다.

진실을 아는 사람: 1
파티1: 1 2
파티2: 2 3
파티3: 3 4

이 경우 1 → 2 → 3 → 4 순서로 진실이 전파된다.
즉 처음에는 1만 알고 있었지만, 결국 4까지 모두 진실을 알게 된다.

이 문제에서 중요한 포인트는 “연쇄 전파”다.
한 번 전파된 사람이 다시 다른 파티에서 전파자가 된다.

 

처음 구현은 사람 기준 그래프를 만들어 BFS를 돌리는 방식이었다.

같은 파티에 있는 사람들을 전부 연결해서 그래프를 만들고, 진실을 아는 사람들을 시작점으로 BFS를 돌려서 진실을 전파했다.

이 방식은 논리적으로는 맞지만 구현이 조금 과해진다.

• 사람 수 기준으로 인접행렬을 만들어야 한다
• 같은 파티 사람들을 전부 서로 연결해야 한다
• BFS에서도 매번 모든 사람을 순회하게 된다

문제의 본질은 “파티 단위 전파”인데, 구현은 “사람 그래프”를 만들어서 한 단계 돌아간 느낌이 들었다.

 

boolean changed = true;
while (changed) {
    changed = false;

    for (int i = 0; i < M; i++) {
        boolean hasTruth = false;

        for (int person : party[i]) {
            if (truth[person]) {
                hasTruth = true;
                break;
            }
        }

        if (!hasTruth) continue;

        for (int person : party[i]) {
            if (truth[person]) continue;
            truth[person] = true;
            changed = true;
        }
    }
}

 

처음 보면 무한루프처럼 보이지만 실제로는 그렇지 않다.

사람은 한 번만 진실을 알게 되기 때문에, 상태가 바뀌는 횟수는 최대 N번이다.
더 이상 새롭게 진실을 아는 사람이 생기지 않으면 반복문이 종료된다.

이 방식은 다음과 같은 장점이 있다.

• 그래프를 따로 만들 필요가 없다
• 코드가 문제의 흐름과 거의 동일하다
• 디버깅이 쉽다

이 문제를 통해 느낀 점은 구현 문제에서 설계의 중요성이다.

처음에는 바로 코드부터 작성했는데, 그러다 보니 불필요하게 그래프를 만들고 코드가 무거워졌다.
반대로 문제를 한 번 정리하고 나서 보면 훨씬 단순한 방식으로 해결할 수 있다.

이 문제를 풀 때 미리 생각해보면 좋은 질문은 다음과 같다.

• 무엇이 전파되는가
• 전파 단위는 무엇인가 (사람인지, 파티인지)
• 전파가 반복되는 구조인가
• 최종적으로 구해야 하는 값은 무엇인가

이 문제는 “사람”이 아니라 “파티”를 기준으로 생각했을 때 훨씬 간단해진다.