[백준] (Swift) 1446번 - 지름길 (dp, 다익스트라, 최단경로 구하기)

🟠 문제 링크

https://www.acmicpc.net/problem/1446

1446번: 지름길

 

🟠 문제 풀이 방법

처음에 내가 접근했던 방법은, 2차원 dp 였다. 이렇게 끝가지 밀고 나갔어도 풀릴거 같긴했다. 근데, 왜 자꾸 생각이 막히지?

처음에는 이렇게 2차원 dp로 문제를 풀려고 했다. 근데 굳이 시작위치를 표현하면서 배열을 거대하게 만들 필요가 없다고 판단되었다. 어차피 도착위치에서 shortcut을 구하면 되기 때문에,, 굳이 시작위치까지 기억해야할 필요가 있을까? 그래서 그냥 1차원 배열로 풀어야겠다고 판단했다.

그래서 판단한게 이렇게! 

distance[위치] 에다가 최소거리를 넣는 방법이다. 최소거리는 어떻게 판별할 것이냐? 만약 shortcut이 없다면, 해당 인덱스 까지의 거리는 인덱스 번호와 일치한다. 그래서 일단 distance 배열에다가 1~D까지 전부 넣어주었다.

지금까지는 distance에 그냥 1부터 차례대로 들어가있다. 근데 위 예제1 에서 처럼, 만약 end point가 50인 곳에 shortcut이 존재한다면, distance[50]은 50이 아니라, 10으로 바꿔주어야한다. 이 과정을 거치게 된다면, distance[50]에 위치한 최소거리는 
distance[49]+1 vs. distance[50]가 된다!

그러면, 여기서 내가 세울 수 있는 로직은

1. 먼저 distance에 1부터 d까지 넣어주기
2. 도착위치가, shortcut이 존재하는 endpoint라면 shortcut넣어주기
   
   • 시작위치로부터 비교해야함. 내가 지금 0에 있을 때, 0이 startpoint에 존재한다면, endpoint에 shortcut을 distance[startpoint] + shortcut으로 !! 해야함!! 그래야 shortcut이 더해진 값이 나옹

 

🟠 소스코드 

나는 하나의 세트 (start, end, shortcut) 을 인덱스 번호로 이용하기 위해서 start, end, shortcut 배열을 따로 만들어서 사용했다!

https://github.com/deslog/Algorithm/blob/main/Algorithm/Boj/1446_%EC%A7%80%EB%A6%84%EA%B8%B8/main.swift

let nd = readLine()!.split(separator: " ").map { Int(String($0))! }
let n = nd[0]
let d = nd[1]
var start = [Int]()
var end = [Int]()
var shortcut = [Int]()
var distance = [Int]()
for i in 0..<d+1 {
    distance.append(i)
}
for _ in 0..<n {
    let temp = readLine()!.split(separator: " ").map { Int(String($0))! }
    start.append(temp[0])
    end.append(temp[1])
    shortcut.append(temp[2])
}

for j in 0..<d+1 {
    if j > 0 {
        distance[j] = min(distance[j-1]+1, distance[j])
    }
    for k in 0..<start.count {
        if j == start[k], end[k] <= d, distance[start[k]]+shortcut[k] < distance[end[k]] {
            distance[end[k]] = distance[start[k]]+shortcut[k]
        }
    }
}

print(distance[d])