[Java] 백준(실버-1) 1325번 - 효율적인 해킹

문제 풀이

---

이번 문제는 너비 우선 탐색인 BFS를 이용해 풀 수 있는 문제이다.

아이디어 도출

이번 문제에서는 컴퓨터를 노드, 연결된 신뢰도를 에지라고 생각하고 BFS 탐색을 수행했다.

A와 B에 관계에 대해서 유의할 점은 다음과 같다.

• A가 B를 신뢰하는 경우 B를 해킹하면 A도 해킹할 수 있는데, 반대의 경우, 즉 A가 B를 신뢰하는 경우 A를 해킹한다고 B가 해킹되는 것은 아니다.
• 한 번의 해킹으로 동시에 해킹할 수 있는 컴퓨터의 수가 가장 많은 수를 찾아야 한다.
• 또한, 동시에 해킹할 수 있는 컴퓨터의 최대 갯수가 동일한 컴퓨터가 여러 대일 수도 있다는 점을 고려한다.

위 내용을 염두에 두고 문제를 풀기위한 아이디어를 정리해보자.

1. BFS 탐색을 수행하면서 해킹할 수 있는 컴퓨터, 즉 신뢰도가 있는 컴퓨터라면 그 수를 카운트한다. (이때, 필자는 카운트배열로 신뢰도를 관리했다.)
2. 컴퓨터별로 신뢰도 수가 담긴 배열에서 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 출력하기 위해 최댓값을 구한다.
3. 최대값과 동일한 컴퓨터의 번호, 인덱스를 순서대로 출력하면 된다.

문제 풀이를 위해 작성한 코드는 아래와 같다.

작성코드

---

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

class Main {    

    // 방문 배열
    static boolean[] visited;
    // 인접 배열
    static List<List<Integer>> list = new ArrayList<>();
    // 노드의 범위 N, 간선의 개수 M 선언
    static int N, M;
    // N개의 컴퓨터간의 신뢰관계를 카운트할 배열
    static int[] count;

    public static void main(String[] args) throws IOException {

        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {

                StringTokenizer st = new StringTokenizer(br.readLine());
                N = Integer.parseInt(st.nextToken());
                M = Integer.parseInt(st.nextToken());

                // 인접배열 초기화
                for(int i=0; i<=N; i++) {
                    list.add(new ArrayList<>());
                }

                // 인접배열에 신뢰도 삽입
                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);
                }

                // 컴퓨터별 총 신뢰도를 담기 위해 초기화
                count = new int[N+1];

                // 컴퓨터별로 방문배열을 초기화해가며, BFS 탐색 수행
                for(int i=1; i<=N; i++) {
                    visited = new boolean[N+1];
                    bfs(i);
                }

                // 모든 컴퓨터 중 가장 높은 신뢰도를 구한다.
                int max = Arrays.stream(count).max().getAsInt();

                // 가장 높은 신뢰도를 가지는 컴퓨터일 경우 오름차순으로 출력한다.
                for(int i=0; i<count.length; i++) {
                    if(count[i] == max) {
                        bw.write(i + " ");
                    }
                }
                
        }

    }
    
    /**
     * BFS 함수
     * 노드별로 너비우선탐색을 하며, 신뢰관계에 놓인 컴퓨터를 탐색하여 해당 컴퓨터의 신뢰도를 갱신한다.
     */
    public static void bfs(int node) {
        Queue<Integer> q = new LinkedList<>();
        q.offer(node);
        visited[node] = true;
        while(!q.isEmpty()) {
            int now = q.poll();
            for(int next : list.get(now)) {
                if(!visited[next]) {
                    visited[next] = true;
                    q.offer(next);
                    count[next]++;
                }
            }
        }
    }
    
}

출처

---

• 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.