[백준] 1325번 : 효율적인 해킹

1325번: 효율적인 해킹

[DFS]

어떻게 시간 초과를 해결해야 할지 막막했던 문제. 동적 프로그래밍 + DFS를 해봤으나 교차 간선이 존재한다면 중복으로 더해지는 정점이 생길 수 있었다. A가 B를 신뢰하는 경우를 A -> B로 놓느냐, A <- B로 놓느냐 크게 상관은 없지만, 이를 가지고 TC, AC가 갈렸다. 처음에는 A <- B로 간선을 놓고 했는데 도저히 TC를 고칠 수 없어서 A -> B로 놓고 기본적인 코드로 진행했더니 맞았다.

 

* 시간초과 코드

    static int DFS(int current){

        if(visit[current]) return connect[current];

        visit[current] = true;
        connect[current] = 1;

        for(int next : list[current])
            connect[current] += DFS(next);

        return connect[current];
    }

# Code </>

public class Main {

    static final int N = 10001;
    static int max = 0;

    static List<Integer>[] list = new ArrayList[N];
    static List<Integer> result = new ArrayList<>();
    static boolean[] visit = new boolean[N];
    static int[] connect = new int[N];

    static void DFS(int current){

        visit[current] = true;

        for(int next : list[current])
            if(!visit[next]) {
                connect[next]++;
                DFS(next);
            }
    }

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

       int n = Integer.parseInt(st.nextToken());
       int m = Integer.parseInt(st.nextToken());

       for(int i=1; i<=n; i++) list[i] = new ArrayList<>();

       for(int i=1; i<=m; i++){
           st = new StringTokenizer(br.readLine());

           int home = Integer.parseInt(st.nextToken());
           int target = Integer.parseInt(st.nextToken());

           list[home].add(target);
       }

       for(int i=1; i<=n; i++) {
           visit = new boolean[N];
           DFS(i);
       }

        for(int i=1; i<=n; i++)
            if (connect[i] > max) {
                max = connect[i];
                result.clear();
                result.add(i);
            } else if (connect[i] == max)
                result.add(i);

       for(int a:result)
           System.out.print(a + " ");
    }
}