10971번: 외판원 순회 2

문제 풀이 아이디어

모든 도시를 방문해야 하므로 완전탐색으로 접근해야 합니다. dfs를 활용해서 풀어보도록 하겠습니다.

하지만 정말로 모든 경우를 탐색하게 되는 경우 시간 초과가 나게 됩니다. 따라서 백트래킹을 활용해서 정답이 될 수 없는 경로는 중간에 제거해주어야 합니다. 제거해야 하는 경로의 조건은 아래와 같습니다.

1. 아직 마지막이 아닌데 출발지로 돌아가려는 경우: 모든 도시를 순회하고 출발지로 돌아가야 하므로 깊이가 N - 1보다 작은데 출발지로 돌아가는 경로는 제거합니다.
2. 이미 최소 비용보다 많은 비용이 소모된 경우: 이미 비용이 초과된 곳은 원하는 경로가 될 수 없으므로 제거합니다.

코드

// dfs 구현
func dfs(start: Int, now: Int, depth: Int) {
    // 모든 도시를 순회한 경우
    if depth == N {
        // cost가 최솟값이면 갱신
        result = min(result, cost)
        return
    }
    
    // 모든 도시를 순회하면서
    for i in 0..<N {
        if !visited[i] && W[now][i] != 0 {
            // 백트래킹 1 : 아직 마지막이 아닌데 출발지로 돌아가는 경우
            if depth < N - 1 && i == start { continue }
            // 백트래킹 2 : 이미 최소 비용보다 많은 비용이 소모된 경우
            if cost + W[now][i] >= result { continue }
            visited[i] = true
            cost += W[now][i]
            dfs(start: start, now: i, depth: depth + 1)
            visited[i] = false
            cost -= W[now][i]
        }
    }
}

// 입력 받기
let N = Int(readLine()!)!
var W = [[Int]]()
for _ in 0..<N {
    W.append(readLine()!.split(separator: " ").map { Int(String($0))! })
}

// dfs를 위한 변수들
var result = Int.max
var visited = Array(repeating: false, count: N)
var cost = 0

// 모든 도시를 출발지로 dfs를 돌린다.
for i in 0..<N {
    dfs(start: i, now: i, depth: 0)
}

print(result)