[BOJ] 1325 효율적인 해킹 - JAVA

1. 문제

1325번: 효율적인 해킹

해커 김지민은 잘 알려진 어느 회사를 해킹하려고 한다. 이 회사는 N개의 컴퓨터로 이루어져 있다. 김지민은 귀찮기 때문에, 한 번의 해킹으로 여러 개의 컴퓨터를 해킹 할 수 있는 컴퓨터를 해킹하려고 한다.

이 회사의 컴퓨터는 신뢰하는 관계와, 신뢰하지 않는 관계로 이루어져 있는데, A가 B를 신뢰하는 경우에는 B를 해킹하면, A도 해킹할 수 있다는 소리다.

이 회사의 컴퓨터의 신뢰하는 관계가 주어졌을 때, 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 출력하는 프로그램을 작성하시오.

---

2. 풀이

문제처럼 b->a가 아닌 a->b로 그래프를 구성했다. 

각 컴퓨터마다 탐색하는데, 탐색할 때마다 visited 배열을 새로 초기화했다.

A B 에서, B를 해킹하면 A도 해킹할 수 있으므로 A가 신뢰하는 여러 컴퓨터들(=A와 연결된 컴퓨터들) 위치의 count배열 값을 +1한다. 

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

public class BOJ_1325_효율적인해킹 {
   static boolean[] visited;
   static ArrayList<Integer>[] link;
   static int[] count;
   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(in.readLine());
      int N = Integer.parseInt(st.nextToken());
      int M = Integer.parseInt(st.nextToken());

      link = new ArrayList[N+1];

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

      int a,b;
      for(int i=0;i<M;i++){
         st = new StringTokenizer(in.readLine());
         a = Integer.parseInt(st.nextToken());
         b = Integer.parseInt(st.nextToken());
         link[a].add(b);
      }

      count = new int[N+1];
      for(int i=1;i<=N;i++){
         visited = new boolean[N+1];
         dfs(i);
      }

      StringBuilder sb = new StringBuilder();
      int max = Arrays.stream(count).max().getAsInt();
      for(int i=1;i<=N;i++){
         if(count[i]==max) sb.append(i).append(' ');
      }
      System.out.println(sb);
   }

   public static void dfs(int now){
      visited[now] = true;
      for(int next:link[now]){
         if(visited[next]) continue;
         visited[next] = true;
         count[next]++;
         dfs(next);
      }
   }
}

---

3. 결과

ㅋㅋㅋㅋㅋㅋㅋㅋㅋ제법 멋지다.. 아주 화려하고ㅎㅎ,,

사실 처음 코드와 맞은 코드의 차이는 거의 없다. 단지 처음에는 문제에 쓰인대로 b->a 형식으로 그래프를 추가했고, 맞은 코드는 a->b형식으로 추가한 게 다르다.

내 생각엔 테스트케이스에 들어가있는 그래프들이 a->b형식으로 했을 때 좀 더 유리한 경우가 많지 않았나 싶다.