[백준] 2098 외판원 순회 Swift

외판원 순회 

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

2098번: 외판원 순회

방문했는지 확인 하는 법 
& 연산자를 통해, 겹치는 1이 있으면 1이상의 값이 나올 것이다 
겹치는 게 없으면 0이 나온다  -> 아직 방문하지 않은 도시

var visited = 011
var i = 100
print(visited & i) // 100

import Foundation

var N = Int(readLine()!)!
var matrix = Array(repeating: Array(repeating: 0, count: N), count: N)
let INF = Int(1e9)
// 비트마스킹 x축, i번쨰 도시 y 축
var dp = Array(repeating: Array(repeating: INF, count: 1<<N), count: N) // 외판원순회에서 2**N개의 경우의 수가 존재함


for i in 0..<N {
    matrix[i] = readLine()!.split(separator: " ").map { Int($0)! }
}

// now, visited
func travel(x:Int, visited:Int) -> Int {
    if visited >= (1 << N)-1 { // 모든 도시를 방문한 경우
        // 현재 노드 'x' -> start node '0' 경로 존재하는 경우
        if matrix[x][0] != 0 {
            return matrix[x][0] // x -> 0 으로 가는 비용
        } else {
            return INF
        }
    }

    if dp[x][visited] != INF {
        return dp[x][visited] // 이미 최소비용이 갱신된 경우
    }

    for i in 1..<N { // 부분집합의 원소 개수
        if visited & (1 << i) == 0 && matrix[x][i] != 0 {
            dp[x][visited] = min(dp[x][visited], travel(x:i, visited: visited | (1 << i)) + matrix[x][i])
        }
    }

    return dp[x][visited]
}

print(travel(x: 0, visited: 1)) // 0000...01 -> 첫번째 도시 방문 처리