백준 14938번 : 서강그라운드 java

이 문제는 다익스트라 알고리즘을 이용하여 탐색하는 알고리즘입니다.

저는 이 문제를 처음 봤을 때 bfs로도 풀 수 있을 것 같았습니다.

그래서 bfs로 문제를 먼저 풀어보았는데 bfs로 문제를 풀 때 탐색하지 않는 부분이 있을 수 있다는 것을 알게 되었습니다.

위의 그림과 같이 그래프가 존재할 때 bfs로 이 문제를 풀면 A -> B 경로를 탐색한 후 바로 A -> C 경로를 탐색합니다.

수색 범위가 10이라고 했을 때 A->C를 통해 C 노드에 이미 접근했기 때문에 A -> B -> C 경로가 더 짧음에도 불구하고
경로가 새로 생성되지 않습니다.

따라서 A -> B -> C -> D 경로로 가면 총 거리가 6이기 때문에 탐색할 수 있는 노드이지만 bfs를 이용하면 탐색할 수
없게 됩니다.

따라서 다익스트라 알고리즘을 이용하여 문제를 해결해야 합니다.

---

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

public class Main {
    static int N, M;
    static int max = Integer.MIN_VALUE;
    static int[] value;
    static int[] dijkstra;
    static boolean[] visited;
    static List<List<Node>> l;

    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());
        int R = Integer.parseInt(st.nextToken());

        value = new int[N+1];
        dijkstra = new int[N+1];
        visited = new boolean[N+1];

        l = new ArrayList<>();
        for(int i = 0; i<=N; i++)
            l.add(new ArrayList<>());

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

        for(int i = 0; i<R; i++){
            st = new StringTokenizer(br.readLine());

            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());
            int len = Integer.parseInt(st.nextToken());

            l.get(A).add(new Node(B, len));
            l.get(B).add(new Node(A, len));
        }

        bfs();

        System.out.println(max);
    }

    static void bfs(){
        for(int i = 1; i<=N; i++) {
            for(int j = 1; j<=N; j++) {
                dijkstra[j] = Integer.MAX_VALUE;
                visited[j] = false;
            }

            int val = bfs(i);
            max = Math.max(max , val);
        }
    }

    static int bfs(int start){
        Queue<Node> q = new LinkedList<>();
        q.offer(new Node(start, 0));
        dijkstra[start] = 0;

        int sum = value[start];

        while(!q.isEmpty()){
            Node num = q.poll();
            int nowIdx = num.idx;
            int nowLen = num.len;

            for(int i = 0; i<l.get(nowIdx).size(); i++){
                Node next = l.get(nowIdx).get(i);

                int nextIdx = next.idx;
                int nextLen = next.len;

                if(nowLen + nextLen>M)
                    continue;
                if(dijkstra[nextIdx] < nowLen + nextLen)
                    continue;

                if(!visited[nextIdx])
                    sum += value[nextIdx];

                dijkstra[nextIdx] = nextLen + nowLen;
                visited[nextIdx] = true;
                q.offer(new Node(nextIdx, nowLen + nextLen));
            }
        }

        return sum;
    }
}
class Node{
    int idx, len;

    Node(int idx, int len){
        this.idx = idx;
        this.len = len;
    }
}

저는 이 문제를 풀 때 처음에 bfs를 이미 이용하여서 그 틀을 이용해 다익스트라 알고리즘을 구현하였기 때문에 위와 같은 코드가 완성되었습니다.

다익스트라 알고리즘을 처음부터 사용한다고 생각하고 문제를 푸시면 더 간결하고 효율적으로 문제를 푸실 수도 있으실 수도 있습니다.