최소경로 - 미래 도시

본 내용은 '이것이 취업을 위한 코딩테스트다 with 파이썬' 책을 기반으로 포스팅 하였습니다.

문제 

저작권 문제가 될 수 있어 문제는 삭제합니다.

 

풀이 코드

// 노드의 개수 및 간선의 개수 입력받기
let input = readLine()!.components(separatedBy: " ").map({Int($0)!})
// 노드의 개수
let n = input[0]
// 간선의 개수
let m = input[1]

// 2차원 배열에 모든 값을 9999999999(무한)으로 초기화
var graph = Array(repeating: Array(repeating: [9999999999], count: n+1), count: n+1)

// 자기자신에서 자기자신으로 가는 비용 0으로 초기화
for a in 1...n {
    for b in 1...n {
        if a == b {
            graph[a][b] = [0]
        }
    }
}

// 각 간선에 대한 정보를 입력받아, 그 값으로 초기화
for _ in 1...m {
    let input = readLine()!.components(separatedBy: " ").map({Int($0)!})
    // A와 B가 서로에게 가는 비용을 1로 초기화
    graph[input[0]][input[1]] = [1]
    graph[input[1]][input[0]] = [1]
}

/*
X = 9999999999

[
[[X], [X], [X], [X], [X], [X]],
[[X], [0], [1], [1], [1], [X]],
[[X], [1], [0], [X], [1], [X]], 
[[X], [1], [X], [0], [1], [1]], 
[[X], [1], [1], [1], [0], [1]], 
[[X], [X], [X], [1], [1], [0]]
]
*/

// 거쳐 갈 노드 K와 최종 목적지 노드 X 입력받기
let input2 = readLine()!.components(separatedBy: " ").map({Int($0)!})
// 최종 목적지
let x = input2[0]
// 거쳐 갈 회사
let k = input2[1]

// 각각의 노드를 거쳐 갈때 드는 최소 비용 계산
for c in 1...n {
    for a in 1...n {
        for b in 1...n {
            graph[a][b] = [min(graph[a][b].first!, graph[a][c].first! + graph[c][b].first!)]
        }
    }
}

// 1번회사에서 K번회사까지 가는 비용 + k번 회사부터 최종 목적지까지 가는 비용
let distance = graph[1][k].first! + graph[k][x].first!

// 결과 출력 
if distance >= 9999999999 {
    print("-1")
} else {
    print(distance)
}

 

문제 풀이

주석 참고