[백준 1446 / Silver5] 지름길 - Java(자바)/Swift(스위프트)

❓문제 설명

작성자 : 김민규
문제 링크 : https://www.acmicpc.net/problem/1446

• 매일 아침, 세준이는 학교에 가기 위해서 차를 타고 D킬로미터 길이의 고속도로를 지난다. 이 고속도로는 심각하게 커브가 많아서 정말 운전하기도 힘들다. 어느 날, 세준이는 이 고속도로에 지름길이 존재한다는 것을 알게 되었다. 모든 지름길은 일방통행이고, 고속도로를 역주행할 수는 없다.
  세준이가 운전해야 하는 거리의 최솟값을 출력하시오.

❗입출력

[입력]
첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하인 양의 정수이고, D는 10,000보다 작거나 같은 자연수이다. 다음 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이가 주어진다. 모든 위치와 길이는 10,000보다 작거나 같은 음이 아닌 정수이다. 지름길의 시작 위치는 도착 위치보다 작다.
[출력]
세준이가 운전해야하는 거리의 최솟값을 출력하시오.
[예시]

🎁 문제 풀이

• arr에 지름길에 대한 정보를 저장합니다.
• dp에 0부터 i까지의 최소거리로 초기화합니다.
• 지름길의 경우와 일반적인 길의 경우를 비교하여 최솟값을 dp에 저장합니다.
• 일반적인 길(지름길이 아닌 경우) 한 칸 전진합니다.
• i에서 출발하는 지름길을 모두 확인합니다.
• 도착점까지의 거리 중에서 일반적으로 갔을 때와 지름길로 갔을 때 중에서 최솟값을 저장합니다.
• dp[D]를 출력하면 최단거리가 출력됩니다.

🖥️ 코드

Java

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

public class Main {
    static int N;
    static int D;
    static ArrayList<int[]> arr = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        D = sc.nextInt();

        for (int i = 0; i < N; i++) {
            int start = sc.nextInt();
            int end = sc.nextInt();
            int dist = sc.nextInt();
            arr.add(new int[]{start, end, dist});
        }

        int[] dp = new int[10000];
        for (int i = 0; i < 10000; i++) {
            dp[i] = i;
        }

        for (int i = 1; i <= D; i++) {
            dp[i] = Math.min(dp[i], dp[i - 1] + 1);
            for (int j = 0; j < N; j++) {
                int[] tmp = arr.get(j);
                dp[tmp[1]] = Math.min(dp[tmp[1]], dp[tmp[0]] + tmp[2]);
            }
        }
        System.out.println(dp[D]);
    }
}

Swift

import Foundation

let input = readLine()!.split(separator: " ").map { Int($0)! }
let N = input[0]
let D = input[1]

var shortcuts = [Int: [[Int]]]()

for _ in 0..<N {
    let line = readLine()!.split(separator: " ").map { Int($0)! }
    let start = line[0]
    let end = line[1]
    let dist = line[2]

    if end > D {
        continue
    }

    shortcuts[start, default: []].append([end, dist])
}

var dp = Array(repeating: Int.max, count: D + 1)
dp[0] = 0

for i in 0..<D {
    dp[i + 1] = min(dp[i + 1], dp[i] + 1)

    if let paths = shortcuts[i] {
        for path in paths {
            let end = path[0]
            let dist = path[1]
            dp[end] = min(dp[end], dp[i] + dist)
        }
    }
}

print(dp[D])

swift코드의 차이점

• shortcuts을 dictionary타입을 이용하여 시작점과 출발점,거리를 저장합니다.
• 도착점이 D보다 크면 저장하지 않습니다.
• i지점에 지름길이 있으면 해당 지름길이 최솟값이면 dp에 저장합니다.