[백준 - 20304] 비밀번호 제작 - C++

분류: bfs, 시작점이 여러 개인 bfs, 비트마스킹 /

 

문제

문제 링크

문제 설명

서강대학교 전산실에서 보안직원으로 일하는 향빈이는 한 통의 이메일을 받게 되었다. 이메일에는 서버 관리자 계정에 대한 비정상적인 로그인 시도가 감지되었다는 내용이 적혀 있었고, 첨부된 파일에는 지금까지 로그인 시도에 사용된 비밀번호 목록이 있었다. 참고로, 서버 관리자 계정의 비밀번호로는 0 이상 N 이하의 정수 중 하나를 사용할 수 있다.

두 비밀번호의 안전 거리는 이진법으로 표현한 두 비밀번호의 서로 다른 자리의 개수로 정의한다. 예를 들어 3을 이진법으로 표현하면 0011, 8을 이진법으로 표현하면 1000이 되고, 이때 서로 다른 자리의 개수는 3개이므로 3과 8의 안전 거리는 3이 된다.

어떤 비밀번호의 안전도는 지금까지 로그인 시도에 사용된 모든 비밀번호와의 안전 거리 중 최솟값으로 정의한다. 예를 들어 지금까지 로그인 시도에 사용된 비밀번호가 3과 4이라고 가정하면, 새로운 비밀번호 8에 대해 3과 8의 안전 거리는 3, 4와 8의 안전 거리는 2이므로 비밀번호 8의 안전도는 2가 된다.

향빈이는 해커가 비밀번호를 알아내기까지의 시간을 최대한 늦추기 위해 현재 사용 중인 관리자 계정 비밀번호의 안전도가 가장 높게끔 바꾸고 싶다. 이때, 안전도가 제일 높은 비밀번호의 안전도를 구하여라.

입력

첫째 줄에 관리자 계정 비밀번호의 최댓값을 나타내는 정수 N이 주어진다. (0≤N≤1 000 000)

둘째 줄에는 로그인 시도에 사용된 비밀번호의 개수를 나타내는 정수 M이 주어진다. (1≤M≤100 000)

셋째 줄에는 로그인 시도에 사용된 비밀번호 값인 정수 p1,p2,⋯,pM이 주어진다. (0≤pi≤N)

출력

안전도가 제일 높은 비밀번호의 안전도를 출력한다.

 

풀이

- 시작점이 여러 개인 BFS

#include <iostream>
#include <queue>
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int N, M; cin >> N >> M;

    int bitLimit = 2;
    while(bitLimit <= N) bitLimit <<= 1;
    
    int dist[bitLimit];
    for(int i=0; i<bitLimit; i++) dist[i] = 0;

    queue<int> Q;
    while(M--) {
        int x; cin >> x;
        dist[x] = 1;
        Q.push(x);
    }

    while(!Q.empty()) {
        int x = Q.front(); Q.pop();
        for(int b = 1; b < bitLimit; (b <<= 1)) {
            int nx = x ^ b;
            if(dist[nx]) continue;
            dist[nx] = dist[x] + 1;
            Q.push(nx);
        }
    }

    int ans = 0;
    for(int i=0; i<=N; i++)
        if(dist[i] > ans) ans = dist[i];
    cout << ans - 1;
}

8미만인 수 중에서 2진수 `000`으로부터 안전거리가 1인 수는 `001, 010, 100`이다.

`001`로부터 안전거리가 1인 수는 `011, 101`이고 이들은 `000`으로부터 안전거리가 2이다.

즉 최단 안전거리끼리 덧셈이 가능하다.  (`A -> C 안전거리` = `A -> B의 안전거리` + `B -> C의 안전거리`)

이를 `000`에서 `011`로 가려면 `001`을 지나야 한다고 이해할 수 있다. 비트 3개로 표현할 수 있는 수(8 미만의 수)들을 그래프로 그리면 다음과 같다.

3비트 그래프

각 간선의 가중치를 안전거리 1로 볼 수 있다. 즉 A -> B의 최단거리가 A -> B의 안전거리이다.

따라서 주어진 M개의 입력을 시작점으로 BFS를 수행하면 주어진 모든 입력으로 부터 가장 멀리 떨어진(안전도가 가장 큰) 수를 알 수 있다.

BFS는 `K`비트로 표현할 수 있는 모든 수에 대한 그래프에서 수행된다. 그래프의 정점은 `K`비트로 표현할 수 있는 수이고 간선은 비트가 1개 차이나는(안전거리가 1인)노드의 연결로 표현된다. 위에서 예시로 든 6면체 형태의 그래프는 `K = 3`인 그래프이다.

 

`K`는 패스워드가 될 수 있는 수의 최댓값(`N`)의 비트 수이다. (`K = ⌊log<sub>2</sub>N⌋ + 1`)

위 코드에서 `N`의 비트수를 계산해 그래프의 크기를 결정한 것이 `bitLimit`이다. (`bitLimit = 2<sup>K + 1</sup>`)

`bitLimit`은 전체 노드의 수를 의미하기도 하고 노드 값의 한계값을 의미하기도 한다.

여기서 참고할 점은 `bitLimit`은 `N`보다 항상 크다는 점이다.(최대 2배 클 수 있다.)

예를 들면 `N = 8 ~ 15`이면 3비트(`K = 3`)이므로 `bitLimit = 16`이다.

 

그래프의 크기가 정해졌다면 BFS로 각 노드의 안전도를 계산해 `dist`에 저장한다.

`dist`에 저장된 안전도의 최댓값이 답이다. (시작점을 1로 했기 때문에 `dist - 1`이 정확한 안전도이다.

 

`x xor b`의 의미는 2진수 `x`에서 `b`자리 수만 flip한다는 의미다. 즉 `nx`는 `x`와 안전거리가 1인 수다.

 

- 범위축소, BFS 순차실행

#include <iostream>
#include <queue>
using namespace std;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int N, M; cin >> N >> M;
    
    bool vis[N + 1];
    for(int i=0; i<=N; i++) vis[i] = false;

    int bitLimit = 2;
    while(bitLimit <= N) bitLimit <<= 1;

    queue<int> Q;
    while(M--) {
        int x; cin >> x;
        vis[x] = true;
        Q.push(x);
    }

    int ans = 0;
    while(!Q.empty()) {
        ans++;
        int size = Q.size();
        while(size--) {
            int x = Q.front(); Q.pop();
            for(int b = 1; b < bitLimit; (b <<= 1)) {
                int nx = x ^ b;
                if(nx > N) continue;
                if(vis[nx]) continue;
                vis[nx] = true;
                Q.push(nx);
            }
        }
    }
    cout << ans-1;
}

N보다 노드를 포함한 큰 모든 노드의 거리를 계산하고 0번 노드에서 N번 노드 중 안전도가 가장 큰 노드를 찾는 것이 비효율적으로 보인다.

여기서 조금 더 고민해 보면 다음과 같은 성질을 알 수 있다.

# N 보다 큰 값은 고려 대상이 아니다.

가장 먼저 드는 생각은 N이상에 대해서도 안전도를 구해야 하는가? 아니다.

`N = 010`이고 `010 -> 100`의 상황을 생각해보자.

`010 -> 110 -> 100`의 경로로 안전거리를 구할 수 있는데 경로에 `N`보다 큰 `110`이 포함된다. 이런 경우를 위해 가장 처음 풀었을 때 `dist`의 범위를 `bitLimit`으로 설정했다.

하지만 출발지와 도착지가 `N`보다 작거나 같다면 항상 `N`보다 작거나 같은 노드만 지나는 최단 경로가 존재한다.

즉 `010 -> 000 -> 100`과 같은 최단 경로가 존재한다는 뜻이다.

따라서 `vis`와 조건문에서 한계값을 N으로 할 수 있다.

 

# dist는 방문과 거리를 모두 저장하고있다. 방문 거리는 BFS 순차 실행으로 가능하다.

첫번째 풀이에서 `dist`배열의 역할은 방문과 거리 기억이다.

거리 계산은 BFS 순차실행으로 하고 중복 계산을 피하기 위해 `vis`배열을 사용할 수 있다. 

int[]에서 bool[]로 메모리를 절약할 수 있다.