[백준] 1325 : 효율적인 해킹 (JAVA)

문제

BOJ 1325 : 효율적인 해킹 - https://www.acmicpc.net/problem/1325

풀이

A 컴퓨터가 B 컴퓨터를 신뢰한다면, B를 해킹했을 때 A도 해킹할 수 있다. 그러므로 B의 인접리스트에 A를 저장해서, B 컴퓨터에 방문했을 시 A로 넘어갈 수 있도록 했다.

그리고 이 문제는 해킹 경로를 구하는 것이 아니라, 해킹이 가능한 최대 컴퓨터 수를 구하는 것이기 때문에 그저 시작점으로부터 몇개의 컴퓨터가 방문 가능한지만 세면 된다!

N개의 컴퓨터가 있기 때문에 각각을 출발지로 dfs를 호출했다. 최댓값을 찾아 StringBuilder로 결과 문자열을 만들어 출력하면 끝.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Main {

    static class Computer{
        int idx;
        ArrayList<Computer> adj;

        public Computer(int idx) {
            this.idx = idx;
            this.adj = new ArrayList<>();
        }
    }

    static Computer[] comps;
    static int n;
    static int m;
    static boolean[] visited;
    static int[] answer;

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

        comps = new Computer[n + 1];
        for (int i = 1; i <= n; i++) {
            comps[i] = new Computer(i);
        }

        for (int i = 0; i < m; i++) {
            inputs = br.readLine().split(" ");
            int a = Integer.parseInt(inputs[0]);
            int b = Integer.parseInt(inputs[1]);
            
 	// A->B 신뢰이면 B를 해킹하면 A도 해킹할 수 있음.
        // B의 인접리스트에 A를 저장
            comps[b].adj.add(comps[a]);
        }

        answer = new int[n + 1];
        for(int i=1; i<=n; i++){
            visited = new boolean[n+1];
            visited[i] = true;
            dfs(i, i);
        }

        int max = 0;
        for(int i=1; i<=n; i++){
            max = Math.max(max, answer[i]);
        }

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

    public static void dfs(int start, int now){

        for (Computer c : comps[now].adj) {
            if (!visited[c.idx]) {
                visited[c.idx] = true;
                dfs(start, c.idx);
                answer[start] ++;
            }
        }

    }
}

정리

✔ 알고리즘 분류 - 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색
✔ 난이도 - ⚪ Silver 2

🤦‍♀️ 오늘의 메모

• 시간초과 때문에 애먹었던 문제,, 한 컴퓨터를 해킹했을 때 해킹 가능한 컴퓨터의 최대 개수만 구하면 되는데, 해킹 경로의 최댓값을 구해야 한다고 생각해서 삽질했다.. 문제를 잘 이해하고 풀 것!

참고 사이트

https://c-king.tistory.com/122