백준 - 외판원 순회 (2098)

let NO_CYCLE = 1000000 * 16 + 1
let INF = NO_CYCLE * 2
let N = Int(readLine()!)!
var weight = [[Int]]()
var dp = Array(repeating: Array(repeating: INF, count: 1 << N), count: N)

for _ in 0..<N {
    let input = readLine()!.split(separator: " ").map { Int(String($0))! }
    weight.append(input)
}

print(tsp(0, 1))

func tsp(_ c: Int, _ v: Int) -> Int {
    if v == (1 << N) - 1 { // 모든 노드 방문
        return weight[c][0] == 0 ? NO_CYCLE : weight[c][0]
    }
    if dp[c][v] != INF { // 방문한 노드라면
        return dp[c][v]
    }
    for i in 0..<N { // 완전 탐색
        if (v & 1 << i) == 0 && weight[c][i] != 0 { // 방문하지 않은 노드이고 갈 수 있는 도시라면
            dp[c][v] = min(dp[c][v], tsp(i, (v | 1 << i)) + weight[c][i])
        }
    }
    return dp[c][v]
}

외판원 문제는 TSP라고 불리는 유명한 문제라고 한다. 나도 알고리즘 수업에서 배웠던 것 같은데 구현까지는 하지 않았던 것 같다.

이 문제에서 N의 크기가 매우 작기 때문에 모든 순서를 완전 탐색해서 정답을 구할 수 있다.

점화식 dp[c][v] 는 현재 도시가 c이고 현재까지 방문한 모든 도시 목록이 v일 때 앞으로 남은 모든 도시를 경유하는 데 필요한 최소 비용 이다.

여기서 모든 도시 목록은 비트(이진수)로 표현할 수 있다. 각 이진수 자릿수를 방문 도시로 보고 방문 시에는 1, 미방문 시에는 0으로 저장한다.

시간 초과 해결 방법

50% 즈음에서 시간 초과가 떠서 열심히 원인을 찾아보니 이 문제 테스트케이스에 마지막에 시작도시로 갈 수 없는 경우가 많다고 한다.

모든 노드를 방문했는데 시작 도시로 돌아갈 수 없는 경우를 따로 체크해주지 않으면 나중에 방문하지 않은 상황으로 판단해서 또 다시 방문하게 되어서 시간 초과가 발생하는 것이었다.

그래서 NO_CYCLE 이라는 상수를 만들어서 시작 도시로 돌아갈 수 없는 경우를 따로 체크해주었다.

관련된 해결 방법은 이 블로그에서 잘 설명해주셨다.