[백준] 1719번 택배 (JAVA)

문제

- 택배 화물이 각 집하장들 사이를 오갈 때, 어떤 경로를 거쳐야 하는지 정해야 함

- 이를 경로표로 정리해야 함

- 경로표에는 한 집하장에서 다른 집하장으로 최단 경로로 화물을 이동시키기 위해 가장 먼저 거쳐야 하는 집하장을 나타냄

 

해결방법

다익스트라 알고리즘을 활용하여 문제를 해결하였다. 다익스트라 알고리즘에 대한 설명을 아래 포스팅을 확인하면 좋을 것 같다.

[알고리즘] 다익스트라 알고리즘 (Dijkstra Algorithm)

다익스트라 기본 코드를 활용하여 문제를 해결하면서, 최단 경로로 확인되었을 때, 이전에 방문한 집하장의 정보를 저장할 수 있도록 2차원 배열 result를 사용하였다. result[][]는 화물을 이동시키기 위해 거쳐야하는 집하장 정보를 저장하는 배열로, 최소 이동 비용을 저장하는 min[] 배열을 update 하면서 같이 update할 수 있도록 하였다. 

위 내용을 제외한 기본적인 틀은 다익스트라 기본 코드로 작성하였다. 아래 포스팅된 문제는 기본적인 다익스트라 코드를 익힐 수 있는 문제이다.

[백준] 1753번 최단경로 (JAVA)

 

코드

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

// Node class
class Node {
    int end;
    int weight;

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

public class Main {
    static int n, m;
    static List<Node>[] list;
    static int[][] result;

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

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        list = new List[n+1];		// 집하장 간 경로 list
        result = new int[n][n];		// 경로표
		
        // 집하장 간 경로를 저장할 배열 초기화
        for(int i = 1; i<=n; i++) {
            list[i] = new ArrayList<>();
        }

        for(int i = 0; i<m; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());
			
            // 단방향이 아니랑 양방향이므로 각각을 저장
            list[start].add(new Node(end, weight));
            list[end].add(new Node(start, weight));
        }
		
        // 1번 집하장부터 n번 집하장까지 최단 경로 검색
        for(int i = 1; i<=n; i++)
            dijkstra(i);
		
        // 경로표 추력
        for(int i = 0; i<n; i++) {
            for(int j = 0; j<n; j++) {
                if (i == j) sb.append("- ");
                else sb.append(result[i][j]).append(" ");
            }
            sb.append("\n");
        }

        System.out.println(sb);
    }
	
    // 다익스트라
    static void dijkstra(int start) {
        boolean[] visit = new boolean[n+1];		// 방문 여부 체크
        int[] min = new int[n+1];			// 최단 경로 값 저장

	// 최단 경로를 저장하기 위해선 MAX 값으로 초기화
        for(int i = 1; i<=n; i++) min[i] = Integer.MAX_VALUE;		

        PriorityQueue<Node> queue = new PriorityQueue<>((o1, o2) -> o1.weight - o2.weight);
        min[start] = 0;				// 시작 집하장은 최단 경로가 0
        queue.add(new Node(start, 0));		// 시작 집하장 queue에 저장

        while (!queue.isEmpty()) {
            Node now = queue.poll();
            // 현재 방문할 정점에 이미 최단 경로로 방문했다면 더이상 방문할 필요 없음
            if(min[now.end] < now.weight) continue;
            if(!visit[now.end]) visit[now.end] = true;		// 방문 처리
            for(int i = 0; i<list[now.end].size(); i++) {
                Node next = list[now.end].get(i);
                // 다음 방문할 정점이 방문하지 않았고, 최단 경로로 방문할 수 있다면
                if(!visit[next.end] && now.weight + next.weight < min[next.end]) {
                    min[next.end] = now.weight + next.weight;		// 최단 경로 값 저장
                    result[next.end-1][start-1] = now.end;		// 경로표 작성
                    queue.add(new Node(next.end, min[next.end]));
                }
            }
        }
    }
}