코딩 테스트 [그래프] - 효율적으로 해킹하기

해커 김지민은 잘 알려진 어느 회사를 해킹하려고 한다. 이 회사에는 신뢰하는 관계와 신뢰하지 않는 관계로 이루어진 N개의 컴퓨터가 있다. A가 B를 신뢰할 경우 B를 해킹하면 A도 해킹할 수 있다. 이 회사의 컴퓨터의 신뢰하는 관계가 주어졌을 때 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 출력하는 프로그램을 작성하시오.

(시간 제한 5초)

---

입력

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

출력

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

예제 입력
5 4		// 컴퓨터 개수(노드), 신뢰 관계 개수(에지)
3 1
3 2
4 3
5 3

예제 출력
1 2

---

1단계 - 문제 분석하기

N과 M의 크기가 작은 편이므로 시간 복잡도와 관련된 제약은 크지 않다.
신뢰 관계가 A, B라면 A가 B를 신뢰한다는 것이다. 또한 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터는 신뢰를 가장 많이 받는 컴퓨터이다.
이 부분을 고려해 문제에 접근해보겠다.

2단계 - 손으로 풀어 보기

1 인접 리스트로 컴퓨터와 신뢰 관계 데이터 그래프를 표현한다.

2 모든 노드로 각각 BFS 탐색 알고리즘을 적용해 탐색을 수행한다. 탐색을 수행하면서 탐색되는 노드들의 신뢰도를 증가시킨다.

3 탐색 종료 후 신뢰도 배열을 탐색해 신뢰도의 최댓값을 Max로 지정하고, 신뢰도 배열을 다시 탐색하면서 Max값을 지니고 있는 노드를 오름차순 출력한다.

3단계 - sudo코드 작성하기

N(노드 개수) M(에지 개수)
answer(정답 배열)
A(그래프 데이터 저장 인접 리스트) visited(방문 유뮤 저장 배열)

for(N의 개수만큼 반복)
	A 인접 리스트의 각 ArrayList 초기화
for(M의 개수만큼 반복)
	A 인접 리스트에 그래프 데이터 저장

for(i -> N의 개수만큼 반복)
{
	visited 배열 초기화
    BFS(i) 실행
}

for(N의 개수만큼 반복)
	answer 배열에서 가장 큰 수 찾아 maxVal에 저장

for(N의 개수만큼 반복)
	answer 배열에서 maxVal과 같은 값을 가진 index를 정답으로 출력
    
BFS
{
	큐 자료구조에 출발 노드 더하기(add)
    visited 배열에 현재 노드 방문 기록
    
    while(큐가 빌 때까지)
    {
    	큐에서 노드 가져오기(poll)
        현재 노드의 연결 노드 중 방문하지 않는 노드로
        큐에 데이터 삽입(add)
        visited 배열에 방문 기록
        answer 배열 값 증가시키기
    }
}

4단계 - 코드 구현하기

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Q47 {
    static int N, M;
    static ArrayList<Integer>[] A;
    static boolean[] visited;
    static int[] answer;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();

        A = new ArrayList[N+1];
        answer = new int[N+1];

        for(int i = 1; i <= N; i++){
            A[i] = new ArrayList<>();
        }

        for(int i = 0; i < M; i++){
            int S = sc.nextInt();
            int E = sc.nextInt();
            A[S].add(E);
        }

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

        int maxVal = 0;
        for(int i = 1; i <= N; i++){
            if(answer[i] > maxVal)
                maxVal = answer[i];
        }

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


    }

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

        while (!queue.isEmpty()){
            int now_Node = queue.poll();
            for(int i : A[now_Node]){
                if(!visited[i]){
                    visited[i] = true;
                    queue.add(i);
                    answer[i]++;
                }
            }
        }
    }
}

---

• Do it! 알고리즘 코딩테스트 자바 편