[백준] no14938:서강그라운드 - 다익스트라(Dijkstra)

문제

 * Input
 * 1. 지역의 수(Node) / 예은이의 수색가능 범위(길이) / 길(Edge)의 갯수
 * 2. 각 지역(Node)별 아이템 수
 * 3. 각 길의 양쪽 지점과 거리가 Edge수 만큼 순차적으로 주어짐
 
 * Output
 * 가장 많은 파밍을 했을 때의 아이템 수

 

문제 링크 : https://www.acmicpc.net/problem/14938

---

원리

 * 풀이법
 * 1. 무방향 그래프 탐색
 * 2. 모든 노드에 대해 가능한 범위 만큼 탐색
 * 3. 탐색 후 더 많이 획득 가능한 경우를 저장
 * 4. 각 지점에 맞게 아이템수 저장(배열)
 * 5. 각 지점 to 지점으로 이동에 필요한 비용 저장(무방향)

 

---

나의 코드

[실패] 시도1. BFS를 이용한 무방향 그래프 탐색 

: 이동 가능 거리의 특징에서 놓친부분이 있다

: 가령, A -> B -> C -> D 지점으로 이동과, A -> B -> E -> D 지점으로 이동을 희망한다고 할 때,

  A -> B -> C -> D이동으로는 이동 거리의 합이 가능한 이동 거리를 초과되나,

  A -> B -> E -> D이동으로는 이동 거리의 합이 가능한 이동 거리를 초과하지 않을 때,

  A에서 B를 이미 방문했기에 일차원 배열 visited[]가 체크되어 후자를 탐색하지 못하는 경우가 발생한다.

 => 따라서, visited는 이차원 배열로 탐색해보자

    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static int Node, Edge, Availability;
    private static StringTokenizer st;
    private static int[] item_status;
    private static Integer[][] field_map; // 길이 없으면 Null
    private static boolean[] visited;

    public static void main(String[] args) throws IOException {
        // 첫 줄 입력 (지점 수, 능력치, 길 수)
        st = new StringTokenizer(br.readLine(), " ");
        Node = Integer.parseInt(st.nextToken());
        Availability = Integer.parseInt(st.nextToken());
        Edge = Integer.parseInt(st.nextToken());

        // 각 지점별 아이템 수 저장
        st = new StringTokenizer(br.readLine(), " ");
        item_status = new int[Node];
        for (int i = 0; i < Node; i++) item_status[i] = Integer.parseInt(st.nextToken());

        // 길 연결
        field_map = new Integer[Node][Node];
        int A, B, Cost;
        for (int i = 0; i < Edge; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            A = Integer.parseInt(st.nextToken()) - 1;
            B = Integer.parseInt(st.nextToken()) - 1;
            Cost = Integer.parseInt(st.nextToken());
            field_map[A][B] = field_map[B][A] = Cost;
        }

        // 각 지점별 탐색 시작
        // 단, 0번 인덱스부터 시작한다. (즉, 문제의 1번지역 == 코드상의 0번 인덱스)
        int result = 0;
        for (int departure = 0; departure < Node; departure++) {
            result = Math.max(result, BFS(departure));
        }

        System.out.println(result);
    }

    private static int BFS(int departure) {
        int result = item_status[departure]; // 처음 내린 지점의 아이템 수
        Deque<Region> dq = new ArrayDeque<>();
        visited = new boolean[Node]; // 각 탐색별로 체크용도
        dq.add(new Region(departure, 0)); // 처음 내린 지점, 이동거리 0

        while (!dq.isEmpty()) {
            /**
             * 이동조건
             * 1. 이동거리가 초과되지 않는지 => 각 노드에 누적되는 이동거리가 Availability를 초과하지 않도록
             * 2. 이동이 가능한 곳인지 => 길이 연결된 곳인지 확인 ([departure][arrival] == null이면 이동불가)
             */
            Region now = dq.poll();

            for (int i = 0; i < Node; i++) {
                if(field_map[now.start][i] == null) continue; // 이동이 불가능한 곳이라면 패스하고 다음지점 탐색

                int next_move = now.move + field_map[now.start][i];

                // 다음 지점으로 이동 가능한 여력이 있을 때
                if (!visited[i] && next_move <= Availability) {
                    visited[i] = true; // 다음 이동 지점 방문 체크
                    result += item_status[i]; // 이동해서 파밍
                    dq.add(new Region(i, next_move)); // 다음지점 탐색, 누적 이동거리
                }
            }
        }
        return result;
    }

    // BFS를 위한 객체용 클래스
    private static class Region {
        private int start, move;

        public Region(int start, int move) {
            this.start = start;
            this.move = move;
        }
    }

  

[실패] 시도 2. 2차원 배열 visited로 탐색하는 방식

: visited의 문제는 맞지만, 2차원 배열의 문제가 아니다.

: 가령 A - B - C - D - E - F 이동과 A - B - ㄱ - D - E - F 이동이 있고 이동 가능 거리가 5라고 하자. 

이때,  A - B 가 1, D - E가 1,  E - F가 1이나

B - C - D 이동이 3이 필요하고,

B - ㄱ - D 이동이 2면 된다고 할 때,

A - B - C - D - E(5)와 A - B - ㄱ - D - E(4) 모두 가능하다.

하지만 A - B - ㄱ - D - E - F입장에선 5로 갈 수 있으므로 가능하지만,

앞서 A - B - C - D - E에서 D - E라는 경로를 이미 방문체크했기에,

A - B - ㄱ - D - E - F 경로는 D 이후로 갈 수가 없게되는 것이다.

 

+) 레퍼런스를 참고하여 찾은 문제해결 : 우선순위 큐를 이용해 이동한 거리가 가장 짧은 순으로 구하면 된다.

    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static int Node, Edge, Availability;
    private static StringTokenizer st;
    private static int[] item_status;
    private static Integer[][] field_map; // 길이 없으면 Null
    private static boolean[][] visited;

    public static void main(String[] args) throws IOException {
        // 첫 줄 입력 (지점 수, 능력치, 길 수)
        st = new StringTokenizer(br.readLine(), " ");
        Node = Integer.parseInt(st.nextToken());
        Availability = Integer.parseInt(st.nextToken());
        Edge = Integer.parseInt(st.nextToken());

        // 각 지점별 아이템 수 저장
        st = new StringTokenizer(br.readLine(), " ");
        item_status = new int[Node];
        for (int i = 0; i < Node; i++) item_status[i] = Integer.parseInt(st.nextToken());

        // 길 연결
        field_map = new Integer[Node][Node];
        int A, B, Cost;
        for (int i = 0; i < Edge; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            A = Integer.parseInt(st.nextToken()) - 1;
            B = Integer.parseInt(st.nextToken()) - 1;
            Cost = Integer.parseInt(st.nextToken());
            field_map[A][B] = field_map[B][A] = Cost;
        }

        int result = 0;
        for (int departure = 0; departure < Node; departure++) {
            result = Math.max(result, BFS(departure));
        }

        System.out.println(result);
    }

    private static int BFS(int departure) {
        int result = item_status[departure]; // 처음 내린 지점의 아이템 수
        Deque<Region> dq = new ArrayDeque<>();
        visited = new boolean[Node][Node]; // 각 탐색별로 체크용도
        dq.add(new Region(departure, 0)); // 처음 내린 지점, 이동거리 0

        while (!dq.isEmpty()) {
            Region now = dq.poll();

            for (int i = 0; i < Node; i++) {
                if (field_map[now.start][i] == null) continue; // 이동이 불가능한 곳이라면 패스하고 다음지점 탐색

                // 다음 지점으로 이동 가능한 여력이 있을 때
                if (!visited[now.start][i]) {
                    int next_move = now.move + field_map[now.start][i];

                    if (next_move <= Availability) {
                        visited[now.start][i] = true; // 다음 이동 지점 방문 체크
                        result += item_status[i]; // 이동해서 파밍
                        dq.add(new Region(i, next_move)); // 다음지점 탐색, 누적 이동거리
                    }
                }
            }
        }
        return result;
    }

    // BFS를 위한 객체용 클래스
    private static class Region {
        private int start, move;

        public Region(int start, int move) {
            this.start = start;
            this.move = move;
        }
    }

---

레퍼런스

참고 링크 : https://steady-coding.tistory.com/90

: comparable 인터페이스를 상속한 객체클래스를 사용한 방식

: 다익스트라를 사용하되, 이동 가능 거리를 염두한 코드

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

public class Main {
    private static int N, M, R; // 지역 수, 가능한 수색 능력, 길의 수
    private static int[] item_status; // 각 지역별 아이템 수
    private static ArrayList<ArrayList<Region>> field;
    private static int[] dist; // 최단거리 배열
    private static boolean[] visited; // 방문확인
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    private static StringTokenizer st;

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

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

        // 각 지역별 아이템 수 입력
        item_status = new int[N+1];
        st = new StringTokenizer(br.readLine());
        for(int i=1 ; i<=N ; i++) item_status[i] = Integer.parseInt(st.nextToken());

        // 각 루트별 비용 입력 (양방향)
        field = new ArrayList<>();
        for(int i=0 ; i<=N ; i++) field.add(new ArrayList<>());
        for(int i=1 ; i<=R ; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());

            field.get(start).add(new Region(end, cost));
            field.get(end).add(new Region(start, cost));
        }

        dist = new int[N+1];
        visited = new boolean[N+1];

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

        bw.write(result + "\n");
        bw.close();    }

    private static int dijkstra(int start) {
        Arrays.fill(dist, Integer.MAX_VALUE);
        Arrays.fill(visited, false);

        PriorityQueue<Region> pq = new PriorityQueue<>();
        pq.add(new Region(start, 0));
        dist[start] = 0;

        while(!pq.isEmpty()) {
            Region now = pq.poll();
            int nowNo = now.regionNo;

            if(!visited[nowNo]) {
                visited[nowNo] = true;

                for(Region region : field.get(nowNo)) {
                    if(!visited[region.regionNo] && dist[region.regionNo] > dist[nowNo] + region.cost) {
                        dist[region.regionNo] = dist[nowNo] + region.cost;
                        pq.add(new Region(region.regionNo, dist[region.regionNo]));
                    }
                }
            }
        }

        int response = 0;
        for(int i=1 ; i<=N ; i++) if(dist[i]<=M) response += item_status[i];

        return response;

    }
}

class Region implements Comparable<Region> {
    int regionNo, cost;

    Region(int regionNo, int cost) {
        this.regionNo = regionNo;
        this.cost = cost;
    }

    @Override
    public int compareTo (Region reg) {
        return cost - reg.cost;
    }
}