[BaekJoon] 1325번 효율적인 해킹 (Java) 문제 풀이 [Sliver 1]

문제

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

1325번: 효율적인 해킹

 

어떻게 풀 것인가?

Java로 풀이를 하게되면 정말 시간초과 때문에 스트레스를 많이 받는 문제이다. DFS, BFS로 문제를 풀었을 때 시간초과가 계속해서 발생한다. 

 

문제를 풀다가 결국엔 다른 사람들의 코드를 참고하여 문제를 풀었다.

결국엔 문제에서 요구하는 것은 한 컴퓨터를 해킹했을 때 해킹 가능한 컴퓨터의 최대 개수만 구하면 된다.

 

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

그리고 이 문제는 해킹 경로를 구하는 것이 아니다. 아마 이 부분때문에 계속해서 시간초과가 발생했다고 생각한다. 해킹이 가능한 최대 컴퓨터 수를 구하는 것이기 때문에 그저 시작점으로부터 몇개의 컴퓨터가 방문 가능한지만 세면 된다!

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

 

풀면서 놓쳤던점

문제의 요점을 크게 놓쳐서 시간초과가 발생했다고 생각한다.

 

이 문제를 통해 얻어갈 것

DFS의 활용

 

내 코드 

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

public class Main {

    public static int N, M;
    public static Computer[] coms;
    public static boolean[] visited;
    public static int[] answer;


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

        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        coms = new Computer[N+1];
        answer= new int[N+1];

        for(int i=0; i<N+1; i++) {
            coms[i] = new Computer(i);
        }

        for(int i=0; i<M; i++) {
            st = new StringTokenizer(br.readLine());
            int p1 = Integer.parseInt(st.nextToken());
            int p2 = Integer.parseInt(st.nextToken());

            coms[p2].list.add(coms[p1]);
        }

        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+1; i++) {
            max = Math.max(max, answer[i]);
        }

        StringBuilder sb = new StringBuilder();

        for(int i=1; i<N+1;i++) {
            if(answer[i] == max) {
                sb.append(i).append(" ");
            }
        }

        System.out.println(sb.toString());
    }
    
    public static void DFS(int original, int now) {
        for(Computer c : coms[now].list) {
            if(!visited[c.idx]) {
                visited[c.idx] = true;
                DFS(original, c.idx);
                answer[original]++;
            }
        }
    }

    public static class Computer{
        int idx;
        ArrayList<Computer> list;			// 접근 가능한 컴퓨터 리스트

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

}

 

참고

https://velog.io/@yanghl98/%EB%B0%B1%EC%A4%80-1325-%ED%9A%A8%EC%9C%A8%EC%A0%81%EC%9D%B8-%ED%95%B4%ED%82%B9-JAVA

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