만득

코딩 공부 정리용

​

© 2021. All rights reserved.

백준 2098 외판원 순회

23 Jun 2021

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

N개의 도시가 있을 때 각 도시간 이동 비용이 주어진다고 하자. 이 때 갈 수 없는 경우는 0으로 나타나고 모든 도시간의 비용은 양의 정수라고 하자. 이 때 중복없이 모든 도시를 지난 후 시작도시로 돌아오는 가장 적은 비용을 구하는 문제이다.

DFS와 DP를 결합해서 문제를 풀어주어야 한다. 이 때 비트마스크를 활용해 여행해온 도시의 상태를 나타내줄 예정이다. 먼저 모든 도시간 이동방법을 고려해주기 위해서 DFS를 이용해서 모든 경로를 탐색할 것이다.

이 때 단순히 모든 경로를 탐색하게 된다면 경우의 수가 너무 많기 때문에 DP를 활용해서 중복 경로를 줄여줄 것이다. 1-2-3 이후에 4라는 도시로 간다고 해보자. 그러면 4부터 모든 도시를 돌아 1로 돌아오는 최단 거리를 dp에 저장해주자. 탐색도중에 우리는 1-3-2 이후에 4라는 도시로 가는 경우가 있을 것이다. 이 때 4부터 모든 도시를 돌아 1로가는 최단 거리는 dp에 저장되어 있기 때문에 두 번 연산해줄 필요가 없다. 이렇듯 겹치는 경로에 대해서는 dp를 활용할 것이다.

그런데 1-5-3 이후에 4라는 도시로 가는 경우를 생각해보자. 이때는 여지껏 거쳐온 도시가 다르기 때문에 위에서 구한 dp값을 쓸 수가 없다. 즉 우리가 어떤 도시를 거쳐왔는지로 dp를 구분시켜줘야 한다는 것이다. 이 때 비트마스크를 사용하여 어떤 도시를 거쳐왔는지를 간단히 정수로 표현할 것이다.

func dfs(d: Int, visited: Int) -> Int {
    if visited == ((1<<n)-1) {
        return cost[d][0] == 0 ? 16_000_001 : cost[d][0]
    }
    else if dp[d][visited] != -1 {
        return dp[d][visited]
    }
    else {
        dp[d][visited] = 16_000_001
        for i in 0..<n {
            if (visited & (1<<i)) == 0 && cost[d][i] != 0 {
                dp[d][visited] = min(dp[d][visited], dfs(d: i, visited: visited | (1<<i)) + cost[d][i])
            }
        }
        return dp[d][visited]
    }
}

자 위의 코드를 한번 보자. visited라는 Int 변수가 나타난다는 것을 알 수 있다. 여기에 비트마스크를 활용할 것이다. 먼저 첫번째 if문을 보면 if visited == (1<<n)-1로 둘을 비교하고있다. (1<<n)-1는 0부터 n-1까지의 bit를 모두 1로 만들어주는 역할을 하고 있다. 이 조건문이 true라면 모든 도시를 탐색했다는 소리이다. 이 경우 우리는 첫번째 도시로 돌아가야하기 때문에 d라는 도시에서 0번째 도시로 가는 경로가 존재할 경우 그 비용을 return 해준다.

자 그러면 마지막 else문을 살펴보자. visited에는 우리가 여지껏 거쳐온 도시의 정보가 들어있다. 따라서 if (visited & 1<<i) 를 하게되면 i번째 도시를 탐색한 적이 있는지 확인할 수 있다. 그래서 만약 도시 이동이 가능하다면 해당 도시로 이동해서 새롭게 dfs를 시행해준다. visited | (1<<i)를 하게되면 visited에 i번째 bit를 1로 만들 수 있다는 것을 명심하자.

let n = Int(readLine()!)!
var dp:[[Int]] = Array(repeating: Array(repeating: -1, count: 1<<n), count: 20)
var cost:[[Int]] = []
for _ in 1...n {
    cost.append(readLine()!.split(separator: " ").map{Int(String($0))!})
}

func dfs(d: Int, visited: Int) -> Int {
    if visited == ((1<<n)-1) {
        return cost[d][0] == 0 ? 16_000_001 : cost[d][0]
    }
    else if dp[d][visited] != -1 {
        return dp[d][visited]
    }
    else {
        dp[d][visited] = 16_000_001
        for i in 0..<n {
            if (visited & (1<<i)) == 0 && cost[d][i] != 0 {
                dp[d][visited] = min(dp[d][visited], dfs(d: i, visited: visited | (1<<i)) + cost[d][i])
            }
        }
        return dp[d][visited]
    }
}
var result = 16_000_001
result = min(result, dfs(d: 0, visited: 1))
print(result)

Related posts