[Swift Algorithm]12978 배달 (서머 윈터 코딩)

programmers.co.kr/learn/courses/30/lessons/12978

코딩테스트 연습 - 배달

풀이방법

그래프문제네요

머리로는 생각이 났지만 풀수가 없어서 개념을 다시 참고했구요

2021/03/06 - [iyOmSd/Title: Algorithm풀이] - [Swift Algorithm] 플로이드 와샬

 

풀면서 이 개념을 쓰면 편하겠다라는 생각은 들었지만..

더 노력해야겠어요

 

아무튼 위의 플로이드 와샬 알고리즘을 사용하면 간단해지죠!

최소거리를 잘계산해줘서

마지막에 1번노드부터 거리이기때문에 0행의 수치를 비교해줬어요

 

범위가 road에서 (a, b, c)가 있을때 c <= 10000 이라고해서

max를 10001이라고하면 실패하는 케이스가 있을 거에요

 

아마도 K의 범위가 50만 이하이기때문에

10001이라고 max를 사용한다면 max + max인 경우가 생길 수 있어요

20002가 저장되어야하는데  (K는 10001을 넘을수있죠)

즉 max보다 큰값이 저장되어야하는데 최솟값으로 10001(max)로 다시 낮아지기때문에

틀린 경우가 있지않을까 생각되요

max의 한계를 높여주니 통과!!(너무 높이면 Int의 범위를 벗어나서 오류주의!)

private func solutionP12978(_ N:Int, _ road:[[Int]], _ k:Int) -> Int {
    var answer = 1
    let max = 500001
    var roadInfo: [[Int]] = (0..<N).map { _ in Array(repeating: max, count: N) }
    roadInfo[0][0] = 0
    
    for r in road {
        let a = r[0] - 1
        let b = r[1] - 1
        let value = r[2]
       
        if roadInfo[a][b] > value || roadInfo[a][b] == max {
            roadInfo[a][b] = value
            roadInfo[b][a] = value
        }
    }

    func 플로이드와샬() {
        for i in 0..<N {
            for j in 0..<N {
                for k in 0..<N {
                    roadInfo[j][k] = min(roadInfo[j][i] + roadInfo[i][k], roadInfo[j][k])
                }
            }
        }
    }
    플로이드와샬()

    for i in 1..<N {
        if roadInfo[0][i] <= k {
            answer += 1
        }
    }
    return answer
}