[BOJ_14938] 서강그라운드

설명

---

정말 간단한 다익스트라 구현 문제 같지만 그렇지만은 않은 것이 해당 부분이 문제 였었습니다. 저는 아래 부분을 풀때, 처음에는 우선  넘긴다음 다음 차례로 들어온 것에 대해서 visited와 함께 걸러내는 식으로 만들었는데요.

 

private static void dijkstra(int start) {
    boolean visited[] = new boolean[N + 1];
    Queue<Data> q = new PriorityQueue<>();
    q.add(new Data(start,0));
    int[] weight = new int[N + 1];
    while (!q.isEmpty()){
        Data now = q.poll();
        if(visited[now.to] || weight[now.to] > M){
            continue;
        }
        visited[now.to] = true;
        ans += items[now.to];
        for (Data next : graph[now.to]){
            if(!visited[next.to]){
                weight[next.to] = weight[now.to] + next.weight;
                q.add(next);
            }
        }
    }
}

 

이렇게 풀면 틀릴 수 밖에 없는 것이 weight 업데이트 자체가 잘 못된 값이 들어와 버리고 PQ에 의해서 다른 큐 weight로 사용 될 수 있었던 정상적인 케이스가 만일 침범되는 이슈가 존재 할 수 있었습니다. 예시로 처음 노드에서 출발한 엣지가 너무 커서 다음 노드가 PQ의 후반부에 배치 되었지만 weight[now.to] 자체는 갈 수 있는 곳이였다고 칩시다. 그런데, 이후에 여러 노드를 거쳐서 들어온 아까 위에서 선정한 다음 노드가 이전 노드와 연결된 weight가 작아서 PQ에 먼저 들어오고 weight가 M보다 커서 아이템을 습득하지 못하는 경우라면..? 이런 경우가 생기기 때문에 아래의 코드로 설정해야 맞습니다.

 

따라서, 처음 들어올 때 부터 분기처리를 적절히 해줘야 weight 배열 초기화를 더럽히지 않을 수 있습니다. 아래와 같이 삽입하는 시점부터 이를 염두해두고 초기화를 진행하니 정답이였습니다.

 

for (Data next : graph[now.to]){
    if(!visited[next.to] && weight[now.to] + next.weight <= M){
        weight[next.to] = weight[now.to] + next.weight;
        q.add(new Data(next.to, weight[next.to]));
    }
}

 

코드

---

package BOJ.Dijkstra;

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

/**
 * @author ksd5653
 *
 * Dijkstra로 도달 할 수 있는 최대 거리를 모두 가본다.
 * 
 * 1번째 입력
 * N = 지역 갯수
 * M = 수색 범위 (dist가 이것보다 작거나 같아야 한다.)
 * R = Edge의 갯수
 * 
 * 2번째 입력
 * N개의 숫자가 각 노드 (지역)의 아이템 갯수를 알려준다.
 *
 * 3번째 입력
 * 각 양 길의 a,b 노드 번호와 길의 길이를 알려준다.
 *
 *
 *
 */
public class BOJ_14938 {
    static class Data implements Comparable<Data>{
        int to; // 갈 곳
        int weight; //길의 길이

        public Data(int to, int weight){
            this.to = to;
            this.weight = weight;
        }

        @Override
        public int compareTo(Data o) {
            return this.weight - o.weight;
        }
    }
    static int[] items; //items 갯수를 담는 배열
    static int N,M,R,ans;
    static List<Data> graph[];

    public static void main(String[] args) throws IOException{
        input();
        int max = 0;
        for (int i = 1; i <= N; i++){
            ans = 0;
            dijkstra(i);
            max = Math.max(max,ans);
        }
        System.out.println(max);
    }

    private static void dijkstra(int start) {
        boolean visited[] = new boolean[N + 1];
        Queue<Data> q = new PriorityQueue<>();
        q.add(new Data(start,0));
        int[] weight = new int[N + 1];

        while (!q.isEmpty()){
            Data now = q.poll();

            if(visited[now.to]){
                continue;
            }

            visited[now.to] = true;
            ans += items[now.to];
            for (Data next : graph[now.to]){
                if(!visited[next.to] && weight[now.to] + next.weight <= M){
                    weight[next.to] = weight[now.to] + next.weight;
                    q.add(next);
                }
            }
        }
    }

    private static void input() throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tk = new StringTokenizer(in.readLine()," ");

        N = Integer.parseInt(tk.nextToken());
        M = Integer.parseInt(tk.nextToken());
        R = Integer.parseInt(tk.nextToken());
        graph = new ArrayList[N + 1];

        for (int i = 0; i <= N; i++){
            graph[i] = new ArrayList<Data>();
        }

        tk = new StringTokenizer(in.readLine()," ");

        items = new int[N + 1];

        for (int i = 1; i <= N; i++) {
            items[i] = Integer.parseInt(tk.nextToken());
        }

        for (int i = 0; i < R; i++){
            tk = new StringTokenizer(in.readLine()," ");
            int from = Integer.parseInt(tk.nextToken());
            int to = Integer.parseInt(tk.nextToken());
            int weight = Integer.parseInt(tk.nextToken());
            graph[from].add(new Data(to,weight));
            graph[to].add(new Data(from,weight));
        }
    }
}

14938번: 서강그라운드