[백준]19538: 루머(java)

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

19538번: 루머

문제

당신은 루머를 믿는가?

한 유명 심리학 실험에서는 사람들에게 두 개의 줄을 보여주고, 어떤 줄이 더 긴지 말하라 했다. 사실 한 사람을 제외하고 나머지는 실험자에 의해 사전에 조작된 사람들이었다. 조작된 사람들은 사실상 더 짧은 줄을 더 길다고 말했다. 주변 모두가 같은 답변을 하자, 진짜 피실험자 또한 짧은 줄이 더 길다고 말했다. 이 실험은 사람들이 주변인의 영향을 강하게 받는다는 것을 보여주었는데, 루머도 이와 같다.

루머는 최초 유포자로부터 시작한다. 최초 유포자는 여러 명일 수 있고, 최초 유포자를 제외하고 스스로 루머를 만들어 믿는 사람은 없다.

매분 루머를 믿는 사람은 모든 주변인에게 루머를 동시에 퍼트리며, 군중 속 사람은 주변인의 절반 이상이 루머를 믿을 때 본인도 루머를 믿는다.

루머를 믿는 순간부터 다른 말은 듣지 않기 때문에, 한번 믿은 루머는 계속 믿는다.

이때, 사람들이 루머를 처음 믿기 시작하는 시간을 알아내 보자.

입력

첫째 줄에 사람의 수 N$N$이 주어진다. (1≤N≤200 000$1 \leq N \leq 200\ 000$) 이는 1$1$번 사람부터 N$N$번 사람까지 있음을 의미한다.

둘째 줄부터 N$N$개의 줄이 주어진다. 이 중 i(1≤i≤N)$i(1 \leq i \leq N)$번째 줄에는 i$i$번 사람의 주변인들의 번호와 입력의 마지막을 나타내는 0이 공백으로 구분되어 주어진다. 번호는 1$1$ 이상 N$N$ 이하의 자연수이고, 같은 줄에 중복된 번호는 없다. 자기 자신이 주변인이거나 일방적으로 주변인인 경우는 없으며, 전체 양방향 주변인 관계는 1 000 000$1\ 000\ 000$개를 넘지 않는다.

다음 줄에는 루머를 퍼뜨리는 최초 유포자의 수 M$M$이 주어진다. (1≤M≤N)$(1 \leq M \leq N)$ 

마지막 줄에는 최초 유포자의 번호가 공백으로 구분되어 주어진다. 최초 유포자의 번호는 중복되지 않는다.

출력

 N$N$개의 정수 t1,t2,⋯,tN$t_1,t_2,\cdots,t_N$을 공백 단위로 출력한다. ti$t_i$는 i$i$번 사람이 루머를 처음 믿기 시작한 시간(분)이며, 충분히 많은 시간이 지나도 루머를 믿지 않을 경우 −1$-1$이다. 최초 유포자는 루머를 0$0$분부터 믿기 시작했다고 생각한다.

예제 입력 1 

7
2 3 0
1 3 0
1 2 4 0
3 5 0
4 0
0
0
2
1 6

예제 출력 1 

0 1 2 3 4 0 -1

---

풀이

처음 접근할 때 시간이 10초인 것을 보고 시간 복잡도를 생각하지 않고 완전탐색 + bfs로 구현하였더니 시간초과가 발생했다.

그래서 생각한 방식은 루머를 전파시킬 아이의 이웃에게 나는 루머를 알고있어 라는 것을 알려주는 것이었다.

neighbor라는 배열을 선언해서 내가 루머를 전파 나랑 연결돼있는 Node들에게 +1을 해주는 것이다.

그럼 해당 Node는 본인 주위에 루머를 알고있는 Node가 몇 개인지 알 수 있고 그게 본인과 연결 된 Node 수의 절반 이상이면 본인도 루머를 알게 된다.

 

전체 코드

package 백준;

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

public class BJ_G4_19538_루머 {
    static int N, M;
    static ArrayList<Integer>[] graph;
    static Queue<Integer> q;
    static int[] time;
    static int[] neighbor;

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

        N = Integer.parseInt(br.readLine());
        graph = new ArrayList[N+1];
        time = new int[N+1];
        neighbor = new int[N+1];
        for(int i=1; i<=N; i++) {
            graph[i] = new ArrayList<>();
            time[i] = -1;
        }

        for(int i=1; i<=N; i++) {
            st = new StringTokenizer(br.readLine());
            while(true) {
                int a = Integer.parseInt(st.nextToken());
                if(a==0) break;
                graph[i].add(a);
            }
        }

        M = Integer.parseInt(br.readLine());
        q = new LinkedList<>();
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<M; i++) {
            int node = Integer.parseInt(st.nextToken());
            time[node] = 0;
            q.add(node);
        }

        bfs();
        for(int i=1; i<=N; i++) {
            ans.append(time[i]);
            if(i!=N) ans.append(" ");
        }
        System.out.printf("%s", ans.toString());
    }

    public static void bfs() {
        while(!q.isEmpty()) {
            int nowNode = q.poll();

            for(int next: graph[nowNode]) {
                //이웃에게 난 루머를 알고있다고 전파
                neighbor[next]++;

                //시간이 기록 돼 있지 않고 && 본인 노드 수 / 2 <= 본인 이웃 노드가 알고있는 루머 수
                if(time[next] == -1 && (graph[next].size() + 1)/2 <= neighbor[next]) {
                    q.add(next);
                    time[next] = time[nowNode]+1;
                }
            }
        }
    }
}