[백준] 5972 택배 배송 (JAVA) - 풀이

문제 분석

• 1번 헛간에서 N번 헛간까지 가는 동안 만나는 모든 소에게 여물을 줘야 함
• 가능한 적은 수의 소를 만나고, 최소한의 여물을 주면서 N번 헛간에 도착할 수 있는 경로 찾아야 함
• 최소 합의 여물 구하기

 

의사 결정

• 우선순위 큐(최소 힙)을 사용해서 최소 여물 수를 먼저 계산할 수 있도록 했습니다.
• 연결된 경로와 가중치(여물)을 저장하기 위해 ArrayList<> arr 배열을 인접 리스트로 사용하여 양방향 간선 정보를 저장했습니다.
• 다익스트라 알고리즘을 사용하여 출발지에서 목적지까지 필요한 최소 여물의 합을 구했습니다.

 

코드 구현

1. Node 객체 선언

이동할 노드와 가중치(여물의 양)을 저장할 Node 객체를 선언했습니다. 우선순위 큐에서 여물의 양이 더 적은 경로를 먼저 처리하기 위해, Comparable 인터페이스를 구현했습니다.

    static class Node implements Comparable<Node> {
        int targetNode, weight;

        Node(int targetNode, int weight) {
            this.targetNode = targetNode;
            this.weight = weight;
        }

        @Override
        public int compareTo(Node n) {
            return Integer.compare(this.weight, n.weight); // 여물의 양을 기준으로 정렬
        }
    }

 

 

2. 헛간과 통로 수 입력 및 배열 선언

헛간끼리 연결된 통로를 입력 받아 배열에 저장했습니다. 통로가 양방향이기 때문에 u에서 v로 가는 경로와 v에서 u로 가는 경로 모두 저장했습니다.

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

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

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());

            arr[u].add(new Node(v, w));
            arr[v].add(new Node(u, w));
        }

 

 

3. 방문 배열과 여물 총 합 배열 선언 및 초기화 

Arrays.fill()를 사용해 모든 헛간의 여물 값을 무한대로 초기화하고, 다익스트라 알고리즘을 사용해 최소 값을 갱신했습니다.

        visited = new boolean[N + 1]; // 방문 여부 체크
        dist = new int[N + 1]; // 최소 여물의 합 저장
        
        Arrays.fill(dist, Integer.MAX_VALUE);

        System.out.println(solution(1, N)); // 1번 헛간에서 N번 헛간까지 최소 여물 출력

 

 

4. solution 함수 상세 설명

현서가 있는 1번 노드와 찬홍이가 있는 N번 노드를 인자로 받아 최소 여물 경로를 계산했습니다.

 

우선순위 큐에 출발 노드를 추가하고, 출발 노드에서 다른 노드으로 가는 통로를 큐에 넣어 탐색했습니다.

 

큐에서 출발 노드를 꺼내서 방문한 노드인지 확인합니다. 방문한 노드이면 continue를 통해 건너뜁니다.

방문하지 않은 노드라면 방문 처리를 하고, for문을 사용해 현재 노드에서 연결된 노드를 확인합니다.

 

연결된 노드가 방문하지 않았고, 현재까지의 경로보다 더 작은 여물을 사용했다면 최소값을 갱신했습니다. 갱신된 경로는 다시 큐에 추가하여 탐색했습니다.

 

탐색이 완료되면 도착 노드를 최소 여물 합 배열에 넣어 출력했습니다.

    static int solution(int start, int end) {
        PriorityQueue<Node> que = new PriorityQueue<>();
        que.add(new Node(start, 0));
        dist[start] = 0;

        while (!que.isEmpty()) {
            Node nowNode = que.poll();
            int now = nowNode.targetNode;

            if (visited[now]) {
                continue; // 이미 방문한 노드는 건너뜀
            }

            visited[now] = true;

            for (Node n : arr[now]) {
                if (!visited[n.targetNode] && dist[n.targetNode] > dist[now] + n.weight) {
                    dist[n.targetNode] = dist[now] + n.weight;
                    que.add(new Node(n.targetNode, dist[n.targetNode]));
                }
            }
        }

        return dist[end];
    }

 

 

 

전체 코드

package Beakjoon.gold;
import java.util.*;
import java.io.*;

public class bj5972 {
    static ArrayList<Node> arr[];
    static boolean[] visited;
    static int[] dist;

    static class Node implements Comparable<Node> {
        int targetNode, weight;

        Node(int targetNode, int weight) {
            this.targetNode = targetNode;
            this.weight = weight;
        }

        @Override
        public int compareTo(Node n) {
            return Integer.compare(this.weight, n.weight);
        }
    }

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

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

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());

            arr[u].add(new Node(v, w));
            arr[v].add(new Node(u, w));
        }

        visited = new boolean[N + 1];
        dist = new int[N + 1];
        
        Arrays.fill(dist, Integer.MAX_VALUE);

        System.out.println(solution(1, N));
    }

    static int solution(int start, int end) {
        PriorityQueue<Node> que = new PriorityQueue<>();
        que.add(new Node(start, 0));
        dist[start] = 0;

        while (!que.isEmpty()) {
            Node nowNode = que.poll();
            int now = nowNode.targetNode;

            if (visited[now]) {
                continue; // 이미 방문한 노드는 건너뜀
            }

            visited[now] = true;

            for (Node n : arr[now]) {
                if (!visited[n.targetNode] && dist[n.targetNode] > dist[now] + n.weight) {
                    dist[n.targetNode] = dist[now] + n.weight;
                    que.add(new Node(n.targetNode, dist[n.targetNode]));
                }
            }
        }

        return dist[end];
    }
}