[백준 1325번] - JAVA

 

• 이 문제를 풀기 위해서는 신뢰 관계를 정확하게 파악해야 합니다.
• 1 2가 신뢰 관계일 때 (1 ➡️ 2) 2가 감염되면 1도 감염이 됩니다. 하지만 1이 감염되면 2는 감염되지 않습니다.
• 즉 신뢰 관계가 양방향이 아닌 단방향이라는 것을 생각하고 문제를 풀어야 합니다.

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

//A가 B를 신뢰한다
//B를 해킹하면 A도 해킹할 수 있다

public class Main{
        
    private static List<Integer>[] graph;
    private static int N;
    private static int M;

     public static void main(String []args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        String input[] = br.readLine().split(" ");
        N = Integer.parseInt(input[0]);
        M = Integer.parseInt(input[1]);

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

        for(int i=0; i<M; i++)
        {
            String[] pcs = br.readLine().split(" ");
            int pc1 = Integer.parseInt(pcs[0]);
            int pc2 = Integer.parseInt(pcs[1]);
            
            //pc1은 pc2를 신뢰한다.
            //pc2가 해킹되면 pc1도 해킹된다.
            //pc1이 다른곳의 pc2인지 탐색을 하는 것이 좋을 것 같다.    
            graph[pc2].add(pc1);
        }
        
        int[] counts = new int[N + 1];
        int max = 0;
        
        for (int i = 1; i <= N; i++) {
            counts[i] = bfs(i);
            max = Math.max(max, counts[i]);
        }
        
       StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= N; i++) {
            if (counts[i] == max) sb.append(i).append(" ");
        }

        System.out.println(sb);
        
        br.close();
     }
     
     private static int bfs(int start)
     {
         boolean[] visited = new boolean[N + 1];
         Queue<Integer> q = new LinkedList<>();
         q.add(start);
         visited[start] = true;
         
         int count = 1;
         while(!q.isEmpty())
         {
             int cur = q.poll();
             for(int next : graph[cur]) {
                 if(!visited[next]) {
                     visited[next] = true;
                     q.add(next);
                     count++;
                 }
             }
         }
         return count;
     }
}

• 우선 입력값을 List에 담아줘야합니다. 
• graph[pc2].add(pc1) : p1은 pc2를 신뢰한다. pc2가 감염되면 pc1이 감염됩니다.
• 모든 노드를 연결했다면 탐색을 수행합니다.
• bfs메서드를 수행하는데 queue에 들어가는 값은 탐색 노드(감염)의 값이라고 생각하시면 됩니다.
• graph[cur] : cur이 감염되면 그 안에 들어있는 모든 값들이 감염됩니다.
• 신뢰 관계로 연결된 노드를 지날때 마다 감염된 것으로 count값을 증가시켜줍니다.
• bfs가 종료되면 count를 배열에 담고 max값을 갱신해줍니다. 
• counts 배열안의 값과 max가 같으면 최댓값입니다. i가 탐색 시작 노드이기 때문에 max과 같은 counts 배열 값이 최대 감염 가능한 노드 값입니다.
• 저는 처음에 BufferedWriter로 출력을 했었는데 시간 초과가 발생해서 StringBuilder를 사용했더니 해결되었습니다.