백준 2098 C++

0번 도시에서 시작하여 모든 도시를 한 번씩 방문하고 다시 0번 도시로 돌아오는 최소 비용을 계산하자.

#include <iostream>
#include <cstring>  // memset 사용
using namespace std;

#define INF 987654321; // 상수로 무한대 값을 정의

int n; // 방문할 도시 갯수
int map[16][16];  // 주어진 비용 행렬
int dp[16][1 << 16];  // 방문한 도시를 2진법으로 저장

// cur: 현재 위치, visit: 방문한 도시를 나타내는 비트마스크
int dfs(int cur, int visit) {
    
    // 모든 도시를 방문했을 경우
    if (visit == (1 << n) - 1) {
        // 시작 도시로 돌아갈 수 없으면 무한대 반환, 아니면 거리 반환
        if (map[cur][0] == 0)
            return INF;
        return map[cur][0];
    }
    
    // 이미 방문한 도시인 경우
    if (dp[cur][visit] != -1)
        return dp[cur][visit];
    
    dp[cur][visit] = INF; // 초기값 설정
    
    // 모든 도시를 순회하며 최소 거리 찾기
    for (int i = 0; i < n; i++) {
        // 길이 없거나 이미 방문한 도시인 경우
        if (map[cur][i] == 0 || (visit & (1 << i)) == (1 << i))
            continue;
        // 현재 도시에서 다음 도시로 이동하고, 해당 도시를 방문한 상태로 재귀 호출
        // 
        dp[cur][visit] = min(dp[cur][visit], map[cur][i] + dfs(i, visit | 1 << i));
    }
    
    return dp[cur][visit];
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    
    cin >> n;
    // 도시 간의 거리 정보 입력
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> map[i][j];
        }
    }
    
    memset(dp, -1, sizeof(dp)); // dp 배열 -1로 초기화
    cout << dfs(0, 1); // 시작도시는 0, 시작도시를 방문했으므로 방문한 도시는 1
    
    return 0;
}

• 도시의 갯수가 16개까지 가능 -> Brute Force를 사용하면 시간 초과
• 방문 여부를 저장해야 하므로 DFS 사용
• 방문 여부 저장 시 비트마스킹 사용
  • 처음 호출: dfs(0, 1)
    • cur = 0 (현재 도시는 0번 도시)
    • visit = 1 (비트마스크로 0번 도시를 방문했음을 나타냄)
  • 재귀 호출: dfs(i, visit | 1 << i)
    • i == 2인 경우
    • cur 업데이트: cur = i = 2 (다음 도시로 이동)
    • visit 업데이트: visit | 1 << i = 1 | (1 << 2) = 1 | 4 = 5 (비트마스크로 0번과 2번 도시를 방문했음을 나타냄)
• memset 함수: 배열을 0 또는 -1로 초기화할 때 유용, algorithm의 fill보다 빠른 속도