[Swift] 백준 17182 우주 탐사선

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

 

 

1. 문제이해

• 행성 간 이동에 걸리는 시간이 2차원 행렬로 주어진다.
• planet[ i ][ j ]은 i 행성에서 j 행성까지 이동하는데 걸리는 시간이다.
• 이미 방문한 행성도 다시 방문 가능
• 출발은 K 행성부터 시작한다.
• 모든 행성을 탐사하는데 걸리는 최소 시간 구하기

2. 접근방법

• 이미 방문한 행성도 다시 방문이 가능하기 때문에 A → B 보다 A → ? → B로 가는 경로가 더 가까울 수 있다.
• planet[i][j]는 i → j 로 직접 가는 시간이 아닌 i → j 로 갈 때 최소 시간이 저장되도록 플로이드 워셜 알고리즘 사용
• planet[i][j]에 각 행성마다 이동하는 최소 시간이 저장되어 있다면 이미 방문한 행성은 방문하지 않도록 dfs+백트래킹으로 모든 행성을 탐사하는데 걸리는 최소 시간을 구할 수 있다.

3. 코드

func solution(){
    let input = readLine()!.split(separator: " ").map{Int(String($0))!}
    let N = input[0]
    let K = input[1]
    var planet = [[Int]]()
    var result = Int.max
    
    var visited = Array(repeating: false, count: N)
    // K 부터 출발
    visited[K] = true
    
    for _ in 0..<N{
        planet.append(readLine()!.split(separator: " ").map{Int(String($0))!})
    }

    func dfs(cur: Int, dept: Int, T: Int){
        if dept == N{
            result = min(result, T)
            return
        }
        
        for i in 0..<N{
            if !visited[i]{
                visited[i] = true
                dfs(cur: i,  dept: dept+1, T: T + planet[cur][i])
                visited[i] = false
            }
        }
    }
    dfs(cur: K, dept: 1, T: 0)
    print(result)
}
solution()