백준 1325번 - 효율적인 해킹 (JAVA)

문제링크

문제

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

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

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

입력

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

출력

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

 

 

 

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 깊이 우선 탐색

 

---

문제 풀이 과정

BFS 문제 풀이 방법으로 문제를 해결 할수 있었다. 이 문제의 핵심은 제일 신뢰도가 높은 컴퓨터를 찾는 문제이다.

서로 연관되어 있는 컴퓨터를 탐색을 하면서 신뢰 하는 컴퓨터의 신뢰도를 증가 시키면서 가장 신뢰도가 높은 컴퓨터를 오름 차순으로 출력 하면 된다.

 

컴퓨터 간의 신뢰도를 ArrayList 형태로 저장 하였다.

list = new ArrayList[n+1];

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

for (int i = 0; i < k; i++) {
    int a = sc.nextInt();
    int b = sc.nextInt();
    list[a].add(b);
}

 

각 컴퓨터가 신뢰하는 컴퓨터의 수를 카운트 하기 위해서 각각의 컴퓨터를 BFS 를 하였다.

 

for (int i = 1; i <= n ; i++) {
    visitied = new boolean[n+1];
    BFS(i);
}

 

BFS 탐색을 한다. 이때 중요한 것은 신뢰도를 증가시키는 것이다. (distance[item]++;)

public static void BFS(int start){
    Queue<Integer> queue = new LinkedList<>();
    queue.add(start);
    visitied[start] = true;

    while (!queue.isEmpty()){
        int cur = queue.poll();
        for(int item : list[cur]){
            if(!visitied[item]){
                visitied[item] = true;
                queue.add(item);
                distance[item]++;
            }
        }
    }
}

 

신뢰도를 담고 있는 distance 배열에서 가장 큰 값을 stream 을 통해서 찾을 수 있다.

 

int max = Arrays.stream(distance).max().getAsInt();

 

max 값을 가지는 인덱스를 찾아서 answer 에 넣은 다음 오름 차순으로 출력해야 되므로 정렬후 출력한다.

 

Collections.sort(answer);
for(int item : answer){
    System.out.print(item + " ");
}

 

전체코드

import java.util.*;

public class Main {
    public static ArrayList<Integer>[] list;
    public static boolean[] visitied;
    public static int[] distance;

    public static void BFS(int start){
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);
        visitied[start] = true;

        while (!queue.isEmpty()){
            int cur = queue.poll();
            for(int item : list[cur]){
                if(!visitied[item]){
                    visitied[item] = true;
                    queue.add(item);
                    distance[item] ++;
                }
            }
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();

        list = new ArrayList[n+1];
        distance = new int[n+1];

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

        for (int i = 0; i < k; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            list[a].add(b);
        }

        for (int i = 1; i <= n ; i++) {
            visitied = new boolean[n+1];
            BFS(i);
        }

        int max = Arrays.stream(distance).max().getAsInt();
        ArrayList<Integer> answer = new ArrayList<>();
        for (int i = 1; i < n+1; i++) {
            if(distance[i] == max){
                answer.add(i);
            }
        }

        Collections.sort(answer);
        for(int item : answer){
            System.out.print(item + " ");
        }
        System.out.println();

    }
}