1325번: 효율적인 해킹

문제

어떤 해커가 회사의 컴퓨터를 해킹하려고 합니다. 이 회사의 컴퓨터는 신뢰하는 관계와 신뢰하지 않는 관계로 이루어져 있습니다. A가 B를 신뢰하는 경우에는 B를 해킹하면 A도 해킹할 수 있습니다. 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 오름차순으로 출력하는 문제입니다.

• 입력: 첫째 줄에 컴퓨터의 수 N (1 ≤ N ≤ 10,000)과 신뢰하는 관계의 수 M (1 ≤ M ≤ 100,000)이 주어집니다. 둘째 줄부터 M개의 줄에 신뢰하는 관계 A, B가 주어집니다.
• 출력: 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 오름차순으로 공백으로 구분하여 출력합니다.

링크: https://www.acmicpc.net/problem/1325

풀이: 방향 그래프 설계와 DFS 탐색

한 컴퓨터를 해킹했을 때 연쇄적으로 감염되는 컴퓨터의 수를 구하는 문제입니다. 모든 컴퓨터를 시작점으로 삼아 탐색을 진행하고, 가장 많이 연결된 컴퓨터를 찾아야 합니다.

1. 간선의 방향 설정 (핵심): 입력으로 주어지는 A B는 "A가 B를 신뢰한다"는 의미이며, 이는 "B를 해킹하면 A도 해킹할 수 있다"는 뜻입니다. 따라서 데이터의 흐름(해킹의 전파 방향)은 B -> A가 됩니다. 인접 리스트 배열을 구성할 때 adj.get(b).add(a) 형태로 방향 그래프를 만들어야 합니다.
2. 완전 탐색 (DFS): 1번 컴퓨터부터 N번 컴퓨터까지 차례대로 깊이 우선 탐색(DFS)을 수행합니다. 특정 컴퓨터 i에서 시작하여 방문할 수 있는 모든 노드의 개수를 세어 cnt[i]에 저장합니다.
3. 시간 초과(TLE) 방지 최적화: 이 문제는 최대 10,000개의 정점에서 매번 탐색을 진행하므로 성능 최적화가 중요합니다. 반복문 내부에서 매번 new boolean[]으로 방문 배열을 생성하면 메모리 할당 및 가비지 컬렉션(GC) 비용이 커져 시간 초과가 발생할 수 있습니다. 따라서 visited 배열을 전역으로 한 번만 할당하고, 매 탐색 직전에 Arrays.fill(visited, false)로 초기화하여 재사용하는 것이 훨씬 효율적입니다.
4. 최댓값 갱신 및 출력: 탐색을 진행함과 동시에 최대로 해킹할 수 있는 컴퓨터 수(max)를 갱신합니다. 모든 탐색이 끝난 후, cnt[i]가 max와 일치하는 컴퓨터 번호만 버퍼에 담아 출력합니다. 1번부터 N번까지 순회하므로 자동 오름차순 정렬됩니다.

코드

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

public class Main {
    static List<List<Integer>> adj = new ArrayList<>();
    static boolean[] visited;

    public static void main(String[] args) throws IOException {
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

       StringTokenizer st = new StringTokenizer(br.readLine());
       int n = Integer.parseInt(st.nextToken());
       int m = Integer.parseInt(st.nextToken());

       for (int i = 0; i <= n; i++) {
          adj.add(new ArrayList<>());
       }

       // 1. 방향 그래프 구성 (B를 해킹하면 A도 해킹됨)
       while (m-- > 0) {
          st = new StringTokenizer(br.readLine());
          int a = Integer.parseInt(st.nextToken());
          int b = Integer.parseInt(st.nextToken());

          adj.get(b).add(a);
       }

       int[] cnt = new int[n + 1];
       
       // 방문 배열을 전역으로 한 번만 생성
       visited = new boolean[n + 1]; 
       int max = 0;

       // 2. 모든 노드에서 탐색 진행
       for (int i = 1; i <= n; i++) {
          // 탐색 전 방문 배열 초기화
          Arrays.fill(visited, false);
          
          cnt[i] = dfs(i);
          
          // 탐색과 동시에 최댓값 갱신
          max = Math.max(max, cnt[i]);
       }

       // 3. 최댓값과 일치하는 노드 번호 출력
       for (int i = 1; i <= n; i++) {
          if (cnt[i] == max) {
             bw.write(i + " ");
          }
       }

       bw.flush();
       bw.close();
       br.close();
    }

    static int dfs(int x) {
       visited[x] = true;
       int ret = 1; // 자기 자신도 해킹된 것으로 간주하므로 1부터 시작
       
       for (int nx : adj.get(x)) {
          if (visited[nx])
             continue;
          
          ret += dfs(nx);
       }

       return ret;
    }
}

알고리즘 분류

그래프 탐색, 깊이 우선 탐색 (DFS), 너비 우선 탐색 (BFS)