[백준 1325] 효율적인 해킹 (Java) - BFS시간초과 엔딩..

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

효율적인 해킹

문제

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

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

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

입력

첫째 줄에, N과 M이 들어온다. N은 10,000보다 작거나 같은 자연수, M은 100,000보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에 신뢰하는 관계가 A B와 같은 형식으로 들어오며, "A가 B를 신뢰한다"를 의미한다. 컴퓨터는 1번부터 N번까지 번호가 하나씩 매겨져 있다.

출력

첫째 줄에, 김지민이 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 오름차순으로 출력한다.

예제 입력 1 복사

5 4
3 1
3 2
4 3
5 3

예제 출력 1 복사

1 2

 

---

풀이

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

public class 효율적인해킹 {
    static int N; // 컴퓨터 수(노드 수)
    static int E; // 신뢰관계 (에지 수)
    static ArrayList<Integer>[] A;
    static int[] dependency; // 의존관계
    static boolean[] visited; // 방문여부
    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()); // 노드개수
        E = Integer.parseInt(st.nextToken()); // 에지개수
        A = new ArrayList[N+1]; // 노드번호 1부터 시작
        dependency = new int[N+1];

        // 각 노드별로 인접리스트 만들어주기
        for(int i=1; i<N+1; i++){
            A[i] = new ArrayList<>();
        }

        // 에지개수만큼 순회하면서 인접노드리스트 관계 값 넣어주기
        for(int i=0; i<E; i++){
            st = new StringTokenizer(br.readLine());
            int node1 = Integer.parseInt(st.nextToken());
            int node2 = Integer.parseInt(st.nextToken());

            A[node1].add(node2); // 단방향 관계
        }

        // 컴퓨터 모두 순회하면서 모두 BFS탐색 수행
        for(int i=1; i<N+1; i++){
            // i번째 노드부터 BFS 탐색
            Queue<Integer> queue = new LinkedList<>();
            visited = new boolean[N+1]; // 방문배열 초기화

            // 시작 노드값 큐에 넣기
            queue.offer(i);

            while (!queue.isEmpty()){
                // 큐가 빌 때까지 수행, 현재 노드 poll
                int now = queue.poll();
                for(int next : A[now]){
                    // 현재노드의 인접리스트 순회하면서 방문하지 않은 노드가 있다면 방문처리 후, dependency 추가 후 큐에 넣음
                    if(!visited[next]){
                        dependency[next]++;
                        queue.add(next);
                    }
                }
            }
        }

        // dependency 배열 값 최댓값 찾기
        int max = Integer.MIN_VALUE;
        for(int i=1; i<N+1; i++){
            max = Math.max(max, dependency[i]);
        }

        for(int i=1; i<N+1; i++){
            if(dependency[i] == max){
                System.out.print(i + " ");
            }
        }

    }
    private static void BFS(int i){
        // i번째 노드부터 BFS 탐색
        Queue<Integer> queue = new LinkedList<>();
        visited = new boolean[N+1]; // 방문배열 초기화

        // 시작 노드값 큐에 넣기
        queue.offer(i);

        while (!queue.isEmpty()){
            // 큐가 빌 때까지 수행, 현재 노드 poll
            int now = queue.poll();
            for(int next : A[now]){
                // 현재노드의 인접리스트 순회하면서 방문하지 않은 노드가 있다면 방문처리 후, dependency 추가 후 큐에 넣음
                if(!visited[next]){
                    dependency[next]++;
                    queue.add(next);
                }
            }
        }
    }
}

• 각 배열의 노드를 시작으로 BFS 탐색수행하면서 방문한 노드번호에 count++해주는 방식
• 시간초과나서 dfs로도 구현해보았지만,,,,,역시 시간초과엔딩
• ....다시 풀어볼예정
• 대체 뭐가문제야