백준[자바]_1325_효율적인해킹_그래프순회_BFS

오늘은 알고리즘 스터디원들과 문제풀이를 하는 도중 다들 이 문제를 어려워 하길래 정리할 겸 풀어보았다. 필자는 별 다른 문제를 못느끼고 문제를 풀었는데, 아무리 해도 안된다는 스터디원들의 말을 듣고, 다른 풀이를 인터넷에 검색해보았다. 한 가지 다른 점이 있다면 인터넷과 팀원들의 풀이는 입력값에 반대 방향으로 그래프를 그렸고, 필자는 입력값 방향 그대로 그래프를 구성했다.  

문제를 보면 그래프가 방향성이 없는 무방향 그래프가 아니라 방향성이 있는 단방향 그래프라는 것은 눈치챘을 것이다.

사실 필자도 구글링을 해보면서 찾아보았지만 시간 초과가 나는 정확한 이유를 모르겠다... 예상가는 바라고 한다면, 1만개의 정점이 10만개의 간선으로 모두 연결이 되어 있는 상태라면, 모든 노드를 탐색해야 하는 이번 문제에 경우 시간초과가 날 수 있을 것이라 생각했다. 기본적으로 방향성이 있는 그래프는 한 정점에서 다른 정점으로 이동하는 방향이 지정되어 있기 때문에 이를 함부로 바꾸면 탐색하는 경우의 수 혹은 연산 횟수가 달라질 수 있을것 같다는 생각이 든다. 모든 그래프가 사이클이 있는 것이 아니고 다양항 구조의 그래프가 존재하기 때문에 입력값에 따라 주어지는 그래프의 구조를 살펴보면 그 경우의 수가 다를 수도 있다는 생각이 든다. 아마 백준에서도 이러한 보장성을 유지한 채로 입력값을 주지 않았을까? 

문제를 풀긴 풀었지만 굉장히 찜찜한 기분이 남기 때문에 지속적으로 기억해두었다가 해결법을 알게되면 돌아와서 내용을 추가하도록 하겠다. 그래프의 종류에 대해 더 알고 싶다면 이 사이트에서 추가적인 공부를 하면 될 것 같다. 

[ 접근 & 문제풀이 ]

• A가 B를 신뢰한다는 말을 그대로 생각해보면 A컴퓨터는 B컴퓨터를 의존한다는 뜻이고, 이를 그래프적인 관점으로 생각해보면 A -> B의 방향성을 가진다는 말이다.
• 우리는 하나의 컴퓨터를 해킹해서 최대한 많은 수의 컴퓨터를 해킹할 수 있는 컴퓨터를 찾아야 한다. 
• 위의 관점에서 볼때, 가장 많은 노드로부터 신뢰받는 즉, 가장 많은 노드로부터 방향성을 가지고 연결되어 있는 노드를 찾아야 한다. 
• 필자는 정답 배열을 따로 만들어서 특정 노드의 인접 노드를 방문할 수 있을 때, 인접 노드 번호를 인덱스로 가지는 정답 배열의 값을 1씩 증가시키면서 count해주었다. 이 방식은 최단거리 배열을 채우는 알고리즘과 유사하며 여러번 연습을 해보았다. 
• 정답 배열에 카운트된 수 중에서 최댓값을 찾고, 정답배열을 다시 탐색하면서 최댓값과 동일한 값을 출력해주면 배열의 인덱스 순서대로 출력이 되기 때문에 문제에서 요구한 오름차순 출력이 가능하다.

[ 소스 코드 ]

package Graph;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class _1325_효율적인해킹 {
    static List<ArrayList<Integer>> list;
    static int ans[];
    static int n, m;
    static boolean visit[];
    public static void main(String[] args) throws Exception{
        // TODO Auto-generated method stub
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        
        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        ans = new int[n+1];
        
        
        list = new ArrayList<ArrayList<Integer>>();
        for(int i=0; i<=n; i++) {
            list.add(new ArrayList<Integer>());
        }
        
        for(int i=0; i<m; i++) {
            st = new StringTokenizer(br.readLine());
            
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            list.get(a).add(b);
        }
        
        //이 값이 최대인 경우의 노드를 해킹하면 최댓값만큼의 컴퓨터를 해킹가능
        //각 노드에서 출발했을때, 최대의 경우의수를 구해야한다.
        //방향이 있는 그래프이기 때문에 사이클을 이루지 않는다면, 특정 노드를 출발노드로 잡았을때, 탐색을 아에 하지 않는 경우가 존재할 수 있다. 
        //따라서 모든 노드를 출발점으로 잡아서 탐색을 진행해야 한다.
        for(int i=1; i<=n;i++) {
            visit = new boolean[n+1];
            BFS(i);
        }
        
        int max = Integer.MIN_VALUE;
        
        //최댓값 찾기
        for(int i=1; i<=n;i++) {
            max = Math.max(max, ans[i]);
        }
        
        for(int i=1; i <=n ; i++) {
            if(ans[i]==max) {
                System.out.print(i + " ");
            }
        }
        
        
    }
    private static void BFS(int i) {
        // TODO Auto-generated method stub
        Queue<Integer> q = new LinkedList<Integer>();
        visit[i] = true;
        q.add(i);
        
        while(!q.isEmpty()) {
            int now = q.poll();
            
            for(int a : list.get(now)) {
                if(!visit[a]) {
                    visit[a] =true;
                    //현재 노드 now에서 a노드로 이동할 수 있다는 것은 
                    //now가 a를 신뢰한다는 뜻이다.
                    ans[a]++;
                    q.add(a);
                }
            }
        }
    }
 
}
 
/*
    A가 B를 신뢰한다. -> A가 B를 방문한다. 
    가장 많은 컴퓨터를 해킹하기 위해서 가장 많은 노드에게 신뢰받는 노드를 찾아야 한다. 
    즉, 가장 많은 노드에게 연결당하는 노드를 찾는다.
    A가 B를 신뢰하는데, B가 C를 신뢰한다고 가정해보자. C를 해킹하면 C를 신뢰하는 A, B 모두 해킹할 수 있다.
*/