[Swift] BOJ 1916 최소비용 구하기

BOJ 1916 최소비용 구하기

 

다익스트라인데, 익숙하지 않아서 아직 잘 안풀리는거 같음.

이 문제는 테케가 적어서 반례를 직접 찾아야 하는게 어려웠음.

 

유독 약한 부분이 그래프다.

 

 

 

샘플 코드

let n = Int(readLine()!)!
        var cities = [[(end: Int, value: Int)]](repeating: [], count: n+1) // label을 달아서 배열 생성
        for _ in 0..<Int(readLine()!)! {
            let d = readLine()!.split(separator: " ").map { Int(String($0))! }
            cities[d[0]].append((d[1], d[2]))
        }
        print(cities)
        let se = readLine()!.split(separator: " ").map { Int(String($0))! }

        var visited = [Bool](repeating: false, count: n+1)
        visited[0] = true

        var graph = [Int](repeating: Int.max, count: n+1)
        graph[se[0]] = 0 // 시작점은 0으로
        visit(se[0])

        func visit(_ current: Int) {
            guard current != se[1] else { return } // 찾는 곳에 도달했다면
            
            visited[current] = true
            for (end, value) in cities[current] {
                graph[end] = min(graph[end], graph[current] + value) // 다익스트라 알고리즘에 의해 업데이트
            }
            
            let next = graph.enumerated()
                .filter({ !visited[$0.offset] }) // 방문하지 않은 노드이면서
                .min(by: { $0.element < $1.element })!.offset // 정렬 했을때 거리가 가장 가까운거 부터 수행
            visit(next) // reculsive!
        }

        print(graph[se[1]])

 

(참고)

https://woongsios.tistory.com/262

백준 1916 최소비용 구하기