[Swift] 백준 14284번 간선 이어가기 2

 

간선 이어가기2 문제

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

 

 

 

 

 

다익스트라 알고리즘으로 해결하면 되는 문제이다.

bfs로 순회하며, dp 방식으로 접근하면 된다. (말은 쉽다..!)

 

현재 정점과 다음 방문할 정점과 비교했을 때,

dp[다음정점]의 가중치가 dp[현재정점]의 가중치+다음 정점 가중치보다 크면 dp[다음정점]현재값으로 업데이트하고, 큐에 추가하는 것이 핵심이다.

 

다익스트라 문제를 풀때는 ..

다익스트라 문제를 풀 때는 아래 내용을 고려하면서 풀면 된다.

 

1. dp 배열의 초기값을 Int.max로 두기

2. 방향그래프인지 무방향 그래프인지 확인해서 딕셔너리 업데이트

3. bfs 시작할 때 시작값의 dp는 0이나 특정 값으로 초기화

4. 방문처리를 따로 안함

5. 스위프트로 bfs 풀 경우 큐(배열)에 removeFirst()를 하기보다는 인덱스로 현재 큐 값을 가져와야 시간초과를 피할 수 있음

6. 이동경로도 출력해야할 경우에는 아래처럼 초기화하고, 방문 리스트를 업데이트해주면 된다.

    - 예시 문제 >>  https://www.acmicpc.net/problem/11779

// DP 초기화
var dp: [(cost: Int, visited: [Int])] = Array(repeating: (cost: Int.max, visited: []), count: n+1)

// 가중치 업데이트할 때 아래처럼 방문한 리스트도 업데이트
dp[nq].visited = dp[q].visited + [nq]

 

 

소스코드

let nm = readLine()!.split(separator: " ").map { Int($0)! }
let (n,m) = (nm[0], nm[1])

var dic: [Int: [(end: Int, weight: Int)]] = [:]
for _ in 0..<m {
    let tmp = readLine()!.split(separator: " ").map { Int($0)! }
    let (st, end, cost) = (tmp[0], tmp[1], tmp[2])
    dic[st, default: []].append((end, cost))
    dic[end, default: []].append((st, cost))
}
let tmp = readLine()!.split(separator: " ").map { Int($0)! }
let (start, end) = (tmp[0], tmp[1])
var dp: [Int] = Array(repeating: Int.max, count: n+1)

var queue: [Int] = [start]
dp[start] = 0

var idx = 0

while queue.count > idx {
    let q = queue[idx]
    
    let nqList = dic[q, default: []]
    for (nq, nweight) in nqList {
        if dp[nq] >= dp[q] + nweight {
            dp[nq] = dp[q] + nweight
            queue.append(nq)
        }
    }
    idx += 1
}
print(dp[end])