백준 19538 (루머) - java

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

 

문제

당신은 루머를 믿는가?

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

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

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

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

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

 

유형 : 위상정렬

 

접근 방식

• 위상정렬적 접근을 하면 된다. 우선 최초 유포자들을 Queue에 넣고 돌리면 된다.
• 주변인한테 루머를 말한다는 것은 연결된 간선을 해제한다 생각하자
• (i번째 노드의 주변 총 간선) - (현재 간선) >= (i번째 노드의 주변 총 간선) / 2 라면 결국 주변인들의 1/2 이상이 루머를 믿는다는 것이다.

코드

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

public class BOJ_19538_루머 {

    static int n;
    static int m;
    static ArrayList<Integer>[] graph;
    static int[] input;
    static int[] count;
    static int[] result;

    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());

        graph = new ArrayList[n+1];
        input = new int[n+1];
        count = new int[n+1];

        for(int i = 1 ; i <= n ; i++) {
            graph[i] = new ArrayList<>();

            st = new StringTokenizer(br.readLine()," ");

            while(true) {
                int next = Integer.parseInt(st.nextToken());

                if(next == 0)
                    break;

                graph[i].add(next);

                input[i] += 1;
                count[i] += 1;
            }
        }

        st = new StringTokenizer(br.readLine()," ");
        m = Integer.parseInt(st.nextToken());


        result = new int[n+1];
        for(int i = 1 ; i <= n ; i++) {
            result[i] = -1;
        }
        Queue<Integer> q = new ArrayDeque<>();
        st = new StringTokenizer(br.readLine()," ");
        for(int i = 1 ; i <= m ; i++) {
            int next = Integer.parseInt(st.nextToken());
            input[next] = 0;
            result[next] = 0;
            q.add(next);
        }

        int[] sec = new int[n+1];

        while(!q.isEmpty()) {
            int cur = q.poll();

            for(int next : graph[cur]) {

                if(input[next] == 0)
                    continue;

                input[next] -= 1;

                sec[next] = Math.max(sec[next], result[cur] + 1);

                if((count[next] - input[next]) * 2 >= count[next]) {
                    input[next] = 0;
                    result[next] = sec[next];
                    q.add(next);
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for(int i = 1 ; i <= n ; i++) {
            sb.append(result[i]+" ");
        }
        System.out.println(sb);

        br.close();
    }
}