백준 1043 거짓말 with 자바

---

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

풀이

먼저 각 파티에 있는 사람끼리 그래프로 연결하고

각 파티마다 진실을 알고 있는 사람이 있는 경우

해당 파티에 있는 나머지 사람들도 진실을 알고 있다고 상태를 변경한 다음

다시 한번 전체 파티를 돌면서

파티에 진실을 알고 있는 사람이 한 명이라도 있는 경우

전체 파티 개수에서 파티 개수를 빼주면 된다

 

전역 변수를 다음과 같이 선언해준다

static int N;
static int M;
static boolean[] visited;           // 최종적으로 진실을 알고있는 사람
static Queue<Integer> knowns;       // 처음에 진실을 알고있는 사람
static Input[] inputs;              // 받은 입력값 저장 (파티 정보)
static LinkedList<Integer>[] nodes; // 사람들을 연결할 그래프

 

파티 정보 값을 저장할 Input 클래스를 선언해준다

파티 인원과 파티원들의 정보를 가지고 있다

// 파티 정보를 저장할 클래스
private static class Input {
    int n;			// 파티 인원
    int[] people;	// 파티원 정보

    public Input(int n, int[] people) {
        this.n = n;
        this.people = people;
    }
}

 

처음에 진실을 알고 있는 사람들의 정보를 knowns에 저장한다

// 처음에 알고있는 사람 저장
for (int i = 0; i < k; i++) {
    int n = Integer.parseInt(st.nextToken());
    knowns.add(n);
}

 

그다음, 

파티의 정보를 받으면서 파티원끼리 서로 그래프로 연결한다
만약 파티의 정보가 다음과 같이 주어졌다면

4 1 2 3 4

1과 2, 2와 3, 3과 4를 그래프로 앞 뒤 사람끼리 연결한다

입력받은 파티 정보를 이용하여 

마지막에 한번 더 탐색을 해야 하므로 파티 정보를 inputs에 저장한다

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

    // 앞 뒤 사람을 서로 연결
    int pre = 0;
    for (int j = 0; j < n; j++) {
        int personNum = Integer.parseInt(st.nextToken());
        people[j] = personNum;

        if (pre != 0) {
            nodes[pre].add(personNum);
            nodes[personNum].add(pre);
        }
        pre = personNum;
    }

    // 입력값을 저장해줌
    Input newInput = new Input(n, people);
    inputs[i] = newInput;
}

 

파티 안에서 진실을 알고 있는 사람이 있는 경우

해당 파티 안에 있는 사람들에게 진실을 전파할 bfs함수를 만든다

static void bfs(int start) {
    Queue<Integer> queue = new LinkedList();
    visited[start] = true;
    queue.add(start);

    while (!queue.isEmpty()) {
        int n = queue.poll();
        LinkedList<Integer> list = nodes[n];
        for (int u : list) {
            if (!visited[u]) {
                visited[u] = true;
                queue.add(u);
            }
        }
    }
}

 

처음에 진실을 알고 있는 사람들을 시작으로 bfs를 돌린다

// 처음에 알고있는 사람 중심으로 bfs
// -> 진실을 알게 되는 사람이 전파됨
visited = new boolean[N + 1];
while (!knowns.isEmpty()) {
    bfs(knowns.poll());
}

그러면 진실을 알고 있는 사람과 같은 파티에 있는 사람들도 진실을 알게 된다

 

파티 정보를 저장한 inputs를 전체 탐색하면서

파티에 한 명이라도 진실을 알고 있는 사람이 있는 경우

전체 파티 개수에서 -1을 해준다

// 입력값을 다시 확인하면서 진실을 알고있는 사람 체크
int total = M;
for (int i = 0; i < M; i++) {
    Input input = inputs[i];
    boolean flag = false;

    for (int j = 0; j < input.n; j++) {
        int n = input.people[j];
        if (visited[n]) {
            flag = true;
            break;
        }
    }

    // 해당 무리중에 진실을 알고 있는 사람이 있다면
    if (flag) total--;
}

 

---

 

전체 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    static int N;
    static int M;
    static boolean[] visited;
    static Queue<Integer> knowns;
    static Input[] inputs;
    static LinkedList<Integer>[] nodes;

    private static class Input {
        int n;
        int[] people;

        public Input(int n, int[] people) {
            this.n = n;
            this.people = people;
        }
    }

    static void bfs(int start) {
        Queue<Integer> queue = new LinkedList();
        visited[start] = true;
        queue.add(start);

        while (!queue.isEmpty()) {
            int n = queue.poll();
            LinkedList<Integer> list = nodes[n];
            for (int u : list) {
                if (!visited[u]) {
                    visited[u] = true;
                    queue.add(u);
                }
            }
        }
    }

    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());
        knowns = new LinkedList();
        inputs = new Input[M];
        nodes = new LinkedList[N + 1];

        for (int i = 1; i <= N; i++) {
            nodes[i] = new LinkedList();
        }

        st = new StringTokenizer(br.readLine());
        int k = Integer.parseInt(st.nextToken());
        for (int i = 0; i < k; i++) {
            int n = Integer.parseInt(st.nextToken());
            knowns.add(n);
        }

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

            int pre = 0;
            for (int j = 0; j < n; j++) {
                int personNum = Integer.parseInt(st.nextToken());
                people[j] = personNum;

                if (pre != 0) {
                    nodes[pre].add(personNum);
                    nodes[personNum].add(pre);
                }
                pre = personNum;
            }

            Input newInput = new Input(n, people);
            inputs[i] = newInput;
        }

        visited = new boolean[N + 1];
        while (!knowns.isEmpty()) {
            bfs(knowns.poll());
        }

        int total = M;
        for (int i = 0; i < M; i++) {
            Input input = inputs[i];
            boolean flag = false;
            for (int j = 0; j < input.n; j++) {
                int n = input.people[j];
                if (visited[n]) {
                    flag = true;
                    break;
                }
            }

            if (flag) total--;
        }

        System.out.println(total);
    }
}