BOJ - 10282번 해킹 문제 Java를 이용한 dijkstra 풀이

요즘 코딩테스트에서 백 엔드 직군의 경우 Java 언어를 사용하도록 C++와 같은 언어 사용에 제약을 두는 분위기인 것 같아서 Java를 이용한 코딩테스트 연습을 이어가고 있습니다.

 

이번 문제는 그 중에서도 다익스트라(dijkstra) 알고리즘을 이용해 풀이해야 하는 문제였는데, 아무래도 오랜만에 푸는 유형이기도 하고, C++를 사용했을 때와는 다른 포인트에서 신경을 써야 하는 경우도 더러 있어 이번 기회에 정리해보려 합니다.

https://www.acmicpc.net/problem/10282

10282번: 해킹

---

문제 설명

최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 그로부터 일정 시간 뒤 a도 감염되고 만다. 이때 b가 a를 의존하지 않는다면, a가 감염되더라도 b는 안전하다.

최흉최악의 해커 yum3이 해킹한 컴퓨터 번호와 각 의존성이 주어질 때, 해킹당한 컴퓨터까지 포함하여 총 몇 대의 컴퓨터가 감염되며 그에 걸리는 시간이 얼마인지 구하는 프로그램을 작성하시오.

 

입력은 일반적인 다익스트라 문제에서 출발 노드, 도착 노드, 간선의 길이 정보가 주어지듯이 주어집니다.

입출력 예시

해킹이 된 컴퓨터에 의존하고 있는 컴퓨터도 시간이 지남에 따라서 해킹되는 점을 미루어 보아 그래프 탐색 관련된 문제임을 파악할 수 있었고

 

해킹이 전파됨에 따라서 걸리는 최소 시간을 구하는 것을 통해 다익스트라로 풀면 되겠다고 생각했습니다.

---

풀이 방식

우선 코드부터 가져오겠습니다.

package boj;

import java.io.*;
import java.lang.reflect.Array;
import java.util.*;

public class BOJ_10282 {
    private static int t;
    private static int n, d, c;
    private static int INF = (int) 1e9;
    private static ArrayList<ArrayList<Edge>> map;
    private static StringBuilder strAns = new StringBuilder();

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

        t = Integer.parseInt(br.readLine());

        while(t != 0){
            st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken());
            d = Integer.parseInt(st.nextToken());
            c = Integer.parseInt(st.nextToken());

            map = new ArrayList<>();
            for(int i = 0; i <= n; i++){
                map.add(new ArrayList<>());
            }

            for(int i = 0; i < d; i++){
                st = new StringTokenizer(br.readLine());
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());
                int cost = Integer.parseInt(st.nextToken());

                map.get(y).add(new Edge(x, cost));
            }
            dijkstra();
            t--;
        }
        System.out.println(strAns);
    }

    private static void dijkstra(){
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        int[] d = new int[n + 1];
        for(int i = 1; i <= n; i++){
            if(i == c){
                d[i] = 0;
                continue;
            }
            d[i] = INF;
        }

        pq.add(new Edge(c, 0));
        while(!pq.isEmpty()){
            Edge e = pq.poll();
            int cur = e.y;
            int dis = e.cost;

            if(d[cur] < dis){
                continue;
            }

            for(int i = 0; i < map.get(cur).size(); i++){
                int nextDis = d[cur] + map.get(cur).get(i).cost;
                int next = map.get(cur).get(i).y;

                if(nextDis < d[next]) {
                    d[next] = nextDis;
                    pq.add(new Edge(next, nextDis));
                }
            }
        }

        int cnt = 0;
        int ans = 0;
        for(int i = 1; i <= n; i++){
            if(d[i] != INF) {
                cnt++;
                ans = Math.max(ans, d[i]);
            }
        }
        strAns.append(cnt + " " + ans + "\n");
    }
    private static class Edge implements Comparable<Edge>{
        int y;
        int cost;

        public Edge(int y, int cost){
            this.y = y;
            this.cost = cost;
        }

        @Override
        public int compareTo(Edge o) {
            return this.cost - o.cost;
        }
    }
}

priority queue를 사용해서 최소 시간 정보를 갖고 있는 컴퓨터를 우선적으로 탐색하는 방식을 통해 시간을 단축할 수 있도록 선택했습니다.

 

Edge라는 별도의 클래스를 만들어 간선의 정보를 표현했는데, 더 적절한 이름이 없을지 생각해봐야 할 것 같습니다.

 

추가적으로 처음에 LinkedList 컬렉션을 사용해 시간 초과 문제를 맞이했는데, ArrayList를 사용해서 해결할 수 있었습니다. 이건 당연히 LinkedList를 사용함에 따라서 발생하는 탐색 시간이 index를 기반으로 탐색하는 ArrayList에 비해 굉장히 느리기 때문이었다고 생각합니다.

 

LinkedList, ArrayList의 차이를 알고 있음에도 이런 포인트를 놓친 것을 보면, 아직 자바로 문제를 풀이하는 경험치가 부족한 것 같아서 계속 문제를 풀어봐야 하지 않을까 싶습니다...