[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 최소비용 구하기