변수 1개로 visited (방문 배열) 나타내기 (ft. 비트마스킹)

알고리즘 문제 풀 때, 비트마스킹을 이용해서 방문 체크를 하면 시간복잡도와 공간복잡도를 개선할 수 있다!!

어떻게 하는지 알아보자😎

 

1. 방문 처리

배열은 왼쪽부터 인덱스가 시작되지만, visited(= 2진수)는 오른쪽부터 인덱스가 시작된다.

따라서 1을 그 인덱스만큼 왼쪽 쉬프트(<<)한 것과 or(|) 연산해줌으로써 비트를 1로 켜주면 그 인덱스를 방문처리 하는거다

 

Ex) {a, b, c, d} 에서 d(idx = 3)를 방문처리 하려면 visited | (1 << 3)

visited | (1 << next); // next : 현재 방문할 정점

 

2. 방문 여부 확인

해당 비트가 켜져있으면 1과 and(&) 연산한 결과가 1이라는 것을 이용하면 된다.

if(visit & (1 << next)) continue; // 방문할 정점(next)이 이미 방문했으면 넘어가기

 

3. 전체(모든 정점)를 다 방문했는지 확인

모든 정점을 다 방문했으면 모든 비트가 1로 켜져있을거니까 이렇게 하면 된다.

if(visited == (1 << N) - 1) ..코드.. // N : 정점 개수

 

4. 사용한 문제 풀이 예시

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

2098번: 외판원 순회

#include <iostream>
#include <cstring>
#include <algorithm>
// #pragma warning(disable:4996)

using namespace std;

const int mx = 16;
const int INF = 1e9;
int n;
int cost[mx][mx], dp[mx][1 << mx]; // dp[현재 도시][현재 방문 상태]

int tsp(int here, int visited) {
    // *** 기저 사례 ***
    if (visited == (1 << n) - 1) { // 모든 도시 방문했을때
        return cost[here][0] ? cost[here][0] : INF; // 여기서 리턴된 값이 이 경로의 비용에 더해짐! (시작도시로 되돌아가는 비용을 리턴)
    }

    // *** 메모이제이션 ***
    int& ret = dp[here][visited];
    if (ret != -1) return ret;

    // *** 로직 (최대값은 최소값부터, 최소값은 최대값부터) ***
    ret = INF;
    for (int i = 0; i < n; ++i) {
        if (cost[here][i] == 0) continue;
        if (visited & (1 << i)) continue; // 이미 방문한 경우
        ret = min(ret, tsp(i, visited | (1 << i)) + cost[here][i]);
    }
    return ret;
}

int main(void) {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    // freopen("C:\\Users\\hyejunseo\\source\\repos\\algo\\algo\\input.txt", "r", stdin);
    // freopen("C:\\Users\\hyejunseo\\source\\repos\\algo\\algo\\output.txt", "w", stdout);

    cin >> n;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> cost[i][j];
        }
    }
    // 초기화 (절대 가질수 없는 값으로)
    memset(dp, -1, sizeof(dp));
    cout << tsp(0, 1) << '\n'; // 같은 경로라면, 해당 경로 내의 어떤 도시에서 출발하든 같은 비용을 가지기 때문에 0번째 도시를 출발도시로 해도 됨 -> 0번째 비트 방문 처리

    return 0;
}

 

 

 

 

 

참고)

https://velog.io/@e_juhee/python-%EB%B0%B1%EC%A4%80-2098-%EC%99%B8%ED%8C%90%EC%9B%90-%EC%88%9C%ED%9A%8C-DP-%EB%B9%84%ED%8A%B8%EB%A7%88%EC%8A%A4%ED%82%B9-lso2bk58