[Baekjoon] 1325 - 효율적인 해킹

📝 문제

 

 

🔑 풀이 과정

· 처음에는 예제 1이 출력이 어떻게 1, 2 나오는지 조차 이해를 못했다. 그러나 항상 그렇듯이 문제에 답이 있다.

"A가 B를 신뢰하는 경우에는 B를 해킹하면, A도 해킹할 수 있다는 소리다."

즉, A가 B를 신뢰하는 경우에는 B에서 A로 향하는 단방향 그래프가 생성된다는 의미이다.

 

· 예제 1을 그림으로 표현하면 다음과 같다.

1을 해킹하면 3, 4, 5 도 다같이 해킹, 2를 해킹하면 3, 4, 5도 다같이 해킹, 3을 해킹하면 4, 5 해킹

4와 5는 해킹할때 같이 해킹되는 컴퓨터 없음.

즉 예제1의 출력이 1, 2가 되는 것이다.

 

· N이 10,000으로 작은 편이므로 각 노드마다 BFS를 실행해준다. 물론 할때마다 방문배열 초기화는 필수다. 그리고 각 컴퓨터 해킹 시 몇대의 컴퓨터가 해킹되는지 저장할 배열을 선언해서 사용해준다. BFS할 때 한 노드를 방문할때마다 카운팅을 증가시키는 방식으로 진행한다.

 

· 이 문제를 처음 제출했을때 오답을 받았다(시간 초과). 그때의 코드는 한 번 BFS가 끝날때마다 for문으로 방문배열을 돌리면서 true인 경우를 카운팅해주고, 또 그 후에 for문으로 방문배열을 또 돌려서 false로 초기화를 시켜줬다. 시간효율이 안좋을 수 밖에 없는 코드...

 

 

 

🔓 답안

import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    static int N;

    static ArrayList<Integer>[] A;
    static boolean[] visited;
    static int[] answers;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        //입력
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken()); //컴퓨터의 개수
        int M = Integer.parseInt(st.nextToken()); //신뢰 관계 개수

        //인접리스트 생성
        A = new ArrayList[N+1];
        for(int i = 1; i <= N; i++){
            A[i] = new ArrayList<>();
        }

        //방문배열 생성
        visited = new boolean[N+1];

        //신뢰 관계 입력받기
        for(int i = 0; i < M; i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            A[b].add(a);
            //A가 B를 신뢰하는 경우: B를 해킹시 A도 해킹 가능이라는 뜻이므로 B에서 A로 방향 그래프를 그린다.
        }

        //BFS 수행
        int max = 0; //해킹할 수 있는 가장 많은 컴퓨터의 수를 저장할 변수
        answers = new int[N+1]; //각 컴퓨터를 해킹할 경우, 해킹할 수 있는 총 컴퓨터의 수를 저장할 배열
        for(int i = 1; i <= N; i++){ //각 컴퓨터별로 해킹
            visited = new boolean[N+1]; //방문배열 초기화
            BFS(i);

            max = Math.max(answers[i], max);
        }

        //answers 배열을 돌면서 max값을 가진 인덱스 출력
        for(int i = 1; i <= N; i++){
            if(answers[i] == max)
                sb.append(i).append(" ");
        }

        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    //BFS 메서드
    static void BFS(int s){
        Queue<Integer> queue = new LinkedList<>();
        visited[s] = true;
        queue.add(s);

        while(!queue.isEmpty()){
            int now = queue.remove();

            for(int n : A[now]){
                if(!visited[n]){
                    answers[s]++;
                    visited[n] = true;
                    queue.add(n);
                }
            }
        }
    }

}

 

 

 

🖤 알고리즘 분류

- 그래프 이론

- 그래프 탐색

- 너비 우선 탐색

- 깊이 우선 탐색