문제 접근

우선, 처음에는 bfs인줄 알았다. 하지만, 10퍼쯤 틀렸다고 나오고 반례를 찾아보았다. bfs는 그냥 거리에 상관없이 이웃한 노드를 먼저 접근하는 알고리즘이다. 따라서, 단순한 bfs로 구하면 안된다....

거리 제약 조건이 붙어있는 경우는 단순 bfs말고, 다익스트라 혹은 플로이드 워샬 같은 거리 기반 알고리즘을 쓰는 것을 생각해보자.

다익스트라 알고리즘이란

오랜만에 다시 다익스트라 문제를 풀려니까 어렴풋이만 기억난다. 그래서 차근차근 정리해보려한다.

• 우선, 우선순위큐를 만들고, 현재 노드a에서 가장 가까운 아직 방문하지 않은 노드b를 고른다
• 현재 노드a까지의 거리(최단거리)와 이 노드a에서 다음 노드b로 넘어가는 거리를 더하고, 이 더한 거리와 b노드의 현재까지의 최단거리(시작점으로부터)를 비교하고, 업데이트해야한다면 업데이트한 값을 담은 Node클래스 객체(노드번호, 현재까지 최단거리)를 우선순위큐에 넣는다.
• 그리고 다시 우선순위큐에서 지금까지의 최단 노드를 뽑는다. 위 작업을 반복한다.

문제는 사실 플로이드 워샬(모든 노드 간의 거리를 N^3의 시간 안에 구하는 (음수 간선을 허용하는)알고리즘)이 더 적합할 것 같다. 굳이 노드별로 다익스트라를 수행하지 않아도 되기 때문이다.
우선, 더 쉽다고 느끼는(많이 봐서 더 친숙해서 그런듯) 다익스트라를 사용해서 풀어보았다.

문제 풀이 (다익스트라)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int N;
    static int M;
    static int R;

    static ArrayList<Node>[] graph;
    static int[] nodeItemInfos;

    static boolean[] isVisited;
    static int[] table;


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

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        R = Integer.parseInt(st.nextToken());

        nodeItemInfos = new int[N + 1];
        graph = new ArrayList[N + 1];
        isVisited = new boolean[N + 1];
        table = new int[N + 1];
        for (int i = 1; i <= N; i++) graph[i] = new ArrayList<>();

        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            nodeItemInfos[i] = Integer.parseInt(st.nextToken());
        }

        for (int i = 0; i < R; i++) {
            st = new StringTokenizer(br.readLine());
            int n1 = Integer.parseInt(st.nextToken());
            int n2 = Integer.parseInt(st.nextToken());
            int d = Integer.parseInt(st.nextToken());
            graph[n1].add(new Node(n2, d));
            graph[n2].add(new Node(n1, d));
        }

        int max = 0;
        for (int i = 1; i <= N; i++) {
            max = Math.max(max, dijkstra(i));
        }

        System.out.println(max);
    }

    private static int dijkstra(int n) {
        Arrays.fill(isVisited, false);
        Arrays.fill(table, Integer.MAX_VALUE);
        PriorityQueue<Node> q = new PriorityQueue<>((node1, node2) -> {
            return node1.d - node2.d;
        });
        q.add(new Node(n, 0));
        table[n] = 0;
        while (!q.isEmpty()) {
            Node curNode = q.poll();
            isVisited[curNode.n] = true; // 한 번 기준 노드가 되면 더이상 고려하지 않을것.
            for (Node next : graph[curNode.n]) {
                int nextDistance = curNode.d + next.d;
                if (!isVisited[next.n] && nextDistance <= table[next.n]) {
                    q.add(new Node(next.n, nextDistance));
                    table[next.n] = nextDistance;
                }
            }
        }

        int count = 0;
        for (int i = 1; i <= N; i++) {
            if (table[i] <= M) count += nodeItemInfos[i];
        }
        return count;
    }

    static class Node {
        final int n;
        final int d;

        Node(int n, int d) {
            this.n = n;
            this.d = d;
        }
    }
}

문제 풀이2 (플로이드 워샬)

플로이드 워샬은 모든 노드에 대해 중간 기준점을 잡아서 더 짧은 거리로 테이블을 갱신하는 알고리즘이다. 음의 간선도 허용한다(이 문제에서는 필요없음).

사실 만들기는 더 쉽다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int N;
    static int M;
    static int R;

    static int[] nodeItemInfos;
    static int[][] table;

    static final int INFINITE = Integer.MAX_VALUE / 2;

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

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        R = Integer.parseInt(st.nextToken());

        nodeItemInfos = new int[N + 1];
        table = new int[N + 1][N + 1];
        for (int i = 1; i <= N; i++) Arrays.fill(table[i], INFINITE);
        for (int i = 1; i <= N; i++) table[i][i] = 0;

        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            nodeItemInfos[i] = Integer.parseInt(st.nextToken());
        }


        for (int i = 0; i < R; i++) {
            st = new StringTokenizer(br.readLine());
            int n1 = Integer.parseInt(st.nextToken());
            int n2 = Integer.parseInt(st.nextToken());
            int d = Integer.parseInt(st.nextToken());
            table[n1][n2] = d;
            table[n2][n1] = d;
        }

        floyd();

        int max = 0;
        for (int n = 1; n <= N; n++) {
            int count = 0;
            for (int i = 1; i <= N; i++) {
                if (table[n][i] <= M) count += nodeItemInfos[i];
            }
            max = Math.max(max, count);
        }
        System.out.println(max);
    }

    private static void floyd() {
        for (int k = 1; k <= N; k++) {
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= N; j++) {
                    int sumDistance = table[i][k] + table[k][j];
                    if (sumDistance < table[i][j]) {
                        table[i][j] = sumDistance;
                    }
                }
            }
        }
    }
}

코드는 더 짧아졌으나, 시간은 똑같았다. 물론 N 크키가 적정 선 안에서 적당히 커진다면 플로이드 워샬이 더 빨라질 것 같다. 참고로, 플로이드 워샬은 N^3 알고리즘이라서 N이 500 이내일때만 사용할 수 있는 걸로 알고 있다.