[백준] 1325 효율적인 해킹 (JAVA)

문제링크:

1325번: 효율적인 해킹

 

 

문제:

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

 

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

 

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

 

 

입력:

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

 

 

출력:

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

 

 

문제이해:

이 문제를 이해하기 위해서 예제 입력 1을 예를들어 설명한다.

대표적으로 1을 예를 들어보면 3->1을신뢰하므로 1을 해킹하면 3을 해킹할 수 있고,

 

4번 5번이 3을 신뢰하므로 4번 5번도 해킹할 수 있어 자신을 제외한 3,4,5 3개를 해킹 할 수 있는 것이다.

 

 

구현방향:

이 문제는 주어진 컴퓨터들 사이의 신뢰 관계를 그래프로 표현하고, 각 컴퓨터를 시작점으로 잡아 얼마나 많은 다른 컴퓨터까지 해킹이 퍼질 수 있는지를 세는 방식으로 해결할 수 있는 문제이다.

 

입력으로 주어지는 a b라는 관계는 “b를 해킹하면 a도 해킹된다”는 의미이다. 따라서 간선은 단순히 a → b 방향이 아니라 b에서 a로 향하는 방향으로 저장해야 한다. 이렇게 해야 특정 노드 b를 시작점으로 탐색을 진행할 때, 실제 해킹 전파가 일어나는 흐름과 일치하게 된다.

 

그래프를 표현할 때는 인접 행렬을 사용하면 메모리 사용량이 O(N^2)으로 매우 커져 제한에 걸리기 쉽다. 따라서 실제로 존재하는 간선만 저장하는 인접 리스트를 사용하는 것이 적절하다. 코드에서는 List<Integer>[] arr 배열을 선언하고 각 칸을 new ArrayList<>()로 초기화한 후, 입력을 받을 때마다 arr[b].add(a)로 관계를 추가한다.

 

탐색은 깊이 우선 탐색(DFS)으로 구현한다. 각 노드를 하나의 시작점으로 두고 DFS를 수행하며, 매번 탐색을 시작하기 전에 visited 배열을 false로 초기화하여 이전 탐색의 흔적이 남지 않도록 한다. 탐색 도중 새롭게 방문한 노드를 발견할 때마다 해당 시작점의 해킹 가능 개수를 하나씩 증가시켜 기록한다.

 

모든 노드를 시작점으로 탐색한 이후에는, result 배열에 기록된 값들 중 가장 큰 값을 찾는다. 이 값이 곧 가장 많은 컴퓨터를 해킹할 수 있는 경우의 수이다. 마지막으로, 최대값과 같은 결과를 가진 노드 번호들을 출력하면 정답이 된다.

 

정답코드:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    static int N, M;
    static List<Integer>[]arr;
    static boolean[] visited;
    static int[] result;
    static int max = 0;


    //dfs탐색
    public static void dfs(int start, int cur) {
        visited[cur] = true;
        for (int next : arr[cur]) {
            if (!visited[next]) {
                result[start]++;
                dfs(start, next);
            }
        }
    }


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        // 초기 세팅
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        // 인접 리스트 초기화
        arr = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) {
            arr[i] = new ArrayList<>();
        }
        visited = new boolean[N + 1];
        result = new int[N + 1];

        for (int i = 0; i < M; i++) {
            String str = br.readLine();
            String[] split = str.split(" ");
            int a = Integer.parseInt(split[0]);
            int b = Integer.parseInt(split[1]);
            arr[b].add(a); // b -> a 간선
        }
        // 세팅 끝

        // dfs 탐색
        for (int i = 1; i <= N; i++) {
            Arrays.fill(visited, false);
            dfs(i, i);
        }

        // 최대값 찾기
        for (int i = 1; i <= N; i++) {
            if (result[i] > max) max = result[i];
        }

        // 최대값 가진 노드 번호 출력
        for (int i = 1; i <= N; i++) {
            if (max == result[i]) System.out.print(i + " ");
        }
    }
}

 

마무리하며:

이번 문제를 풀면서 처음에는 인접 행렬로 구현하였다가 메모리 초과를 경험하였다. 노드 수가 많을 때 인접 행렬은 모든 가능한 간선을 저장하기 때문에 불필요하게 큰 공간을 차지하게 된다. 반면 인접 리스트는 실제 존재하는 간선만을 저장하므로 메모리 사용을 크게 줄일 수 있었다. 이 과정을 통해 단순히 정답을 맞히는 것에 그치지 않고, 입력 크기와 메모리 제약을 고려하여 적절한 자료구조를 선택하는 자세가 필요하다는 점을 배울 수 있었다.

 

감사합니다.