[Algorithm] 백준 - 2098번 외판원 순회 (Swift)

문제 소개

풀이 과정

모든 도시를 순회하게 된다면 n!의 경우의 수가 있으므로 16! = 20조 정도의 경우의 수가 나오니 모든 경우의 수를 순회하는 것은 불가능하다. dp와 비트마스킹을 통해서 방문한 곳을 확인해야 한다. 또한 기존의 순회의 개념을 그대로 가져와서 dfs를 활용하기로 했다. 

 

아래 부분이 메인 로직이라고 할 수 있는데, var dp = Array(repeating: Array(repeating: 16_000_000, count: 1<<16), count: 16) 이러한 식으로 dp를 선언해주고 만약 4개의 노드가 있는 그래프라면 dp[0][0001]을 생각해보면  dp[2][0101]에서의 최솟값 + 0 → 2 로 가는 비용이 될 것이다.

    for i in 0..<n {
        guard w[now][i] != 0 && visited & 1<<i == 0 else { continue }
        dp[now][visited] = min(dp[now][visited], w[now][i] + dfs(i, visited | 1 << i))
    }

 

첫번째 풀이

아래와 같이 문제를 풀었지만... 시간초과가 나고 말았다.

let n = Int(readLine()!)!
var w = Array(repeating: [Int](), count: n)

for i in 0..<n {
    w[i] = readLine()!
            .components(separatedBy: " ")
            .compactMap { Int($0) }
}

var dp = Array(repeating: Array(repeating: 16_000_000, count: 1<<16), count: 16)

func dfs(_ now: Int, _ visited: Int) -> Int {
    if visited == (1 << n) - 1 {
        return w[now][0] == 0 ? 16_000_000 : w[now][0]
    }
    guard dp[now][visited] == 16_000_000 else { return dp[now][visited] }
    for i in 0..<n {
        guard w[now][i] != 0 && visited & 1<<i == 0 else { continue }
        dp[now][visited] = min(dp[now][visited], w[now][i] + dfs(i, visited | 1 << i))
    }
    
    return dp[now][visited]
}

print(dfs(0, 1))

// 입력값
// 10
// 0 1 1 1 1 1 1 1 1 1
// 1 0 1 1 1 1 1 1 1 1
// 0 1 0 1 1 1 1 1 1 1
// 0 1 1 0 1 1 1 1 1 1
// 0 1 1 1 0 1 1 1 1 1
// 0 1 1 1 1 0 1 1 1 1
// 0 1 1 1 1 1 0 1 1 1
// 0 1 1 1 1 1 1 0 1 1
// 0 1 1 1 1 1 1 1 0 1
// 0 1 1 1 1 1 1 1 1 0

// 결과
// ans: 10
// cnt: 410794

 

문제점 해결

문제점은 바로 최댓값인 16000000으로 방문판단도 했는데, 조건을 만족하지 않더라도 16000000을 반환하기 때문에 불필요한 계산이 늘어나는 것이었다. 아래와 같은 입력값을 넣게되면 방문판단을 최댓값으로만 하게되면 약 41만회 실행하게 되고, 수정한 코드는 약 9천회 실행이 되어 큰 속도 차이가 있었다.

10
0 1 1 1 1 1 1 1 1 1
1 0 1 1 1 1 1 1 1 1
0 1 0 1 1 1 1 1 1 1
0 1 1 0 1 1 1 1 1 1
0 1 1 1 0 1 1 1 1 1
0 1 1 1 1 0 1 1 1 1
0 1 1 1 1 1 0 1 1 1
0 1 1 1 1 1 1 0 1 1
0 1 1 1 1 1 1 1 0 1
0 1 1 1 1 1 1 1 1 0

 

여기서 내가 좀 헤깔렸던 부분은 최댓값이 중복되는 부분은 아래 두 부분이라고 생각했다. 그래서 단순하게 아래와 같이 수정해주면 해결이 될 줄 알았다.

// 수정 전
return dp[now][visited]

// 수정 후
return dp[now][visited] == 16_000_000 ? 20_000_000 : dp[now][visited]

큰 값이 반환되면 이후 경로 탐색에서 동일한 상태에 대해 항상 큰 값을 반환하여 경로 탐색이 비효율적으로 된다.

 

최종 코드

아래와 같이 minCost를 두어 해결하였다.

let n = Int(readLine()!)!
var w = Array(repeating: [Int](), count: n)

for i in 0..<n {
    w[i] = readLine()!
            .components(separatedBy: " ")
            .compactMap { Int($0) }
}

var dp = Array(repeating: Array(repeating: 0, count: 1 << 16), count: 16)

func dfs(_ now: Int, _ visited: Int) -> Int {
    cnt += 1
    if visited == (1 << n) - 1 {
        return w[now][0] == 0 ? 16_000_000 : w[now][0]
    }
    guard dp[now][visited] == 0 else { return dp[now][visited] }
    var minCost = 16_000_000
    for i in 0..<n {
        guard w[now][i] != 0 && visited & 1 << i == 0 else { continue }
        minCost = min(minCost, dfs(i, visited | 1 << i) + w[now][i])
        dp[now][visited] = minCost
    }
    
    return minCost
}

print(dfs(0, 1))

// 입력값
// 10
// 0 1 1 1 1 1 1 1 1 1
// 1 0 1 1 1 1 1 1 1 1
// 0 1 0 1 1 1 1 1 1 1
// 0 1 1 0 1 1 1 1 1 1
// 0 1 1 1 0 1 1 1 1 1
// 0 1 1 1 1 0 1 1 1 1
// 0 1 1 1 1 1 0 1 1 1
// 0 1 1 1 1 1 1 0 1 1
// 0 1 1 1 1 1 1 1 0 1
// 0 1 1 1 1 1 1 1 1 0

// 결과
// ans: 10
// cnt: 9226