백준 20304번 [비밀번호 제작](C++) -yes6686- 티스토리

백준 문제 풀이: 20304 (비밀번호 제작)

---

문제 링크: https://www.acmicpc.net/problem/20304

문제 설명:

0부터 N까지의 숫자 중 보안상 사용할 수 없는 금지 번호들이 주어졌을 때, 가장 안전한 비밀번호를 선택하려 합니다. 안전도는 현재 선택한 비밀번호와 금지된 숫자들 사이의 XOR 거리 중 최소값으로 정의됩니다. 즉, 금지된 번호들과 가장 멀리 떨어진 비밀번호(= 최소 XOR 거리가 최대인 숫자)를 찾아 그 최소 XOR 거리를 출력하는 문제입니다.

---

문제 해결 코드

// BFS 기반 XOR 거리 확산을 통해 안전도가 가장 높은 숫자를 찾는 코드
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

int visited[3000001];
int n;

void bfs(int start) {
    queue<pair<int, int>> q;
    q.push({start, 1});
    visited[start] = 1;

    while (!q.empty()) {
        int cur = q.front().first;
        int depth = q.front().second;
        q.pop();

        // 모든 비트 위치에 대해 XOR
        for (int i = 1; i <= n; i *= 2) {
            int next = cur ^ i;
            if (next > n) continue;
            if (visited[next] == 0 || visited[next] > depth + 1) {
                visited[next] = depth + 1;
                q.push({next, depth + 1});
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
    int m;
    cin >> m;

    for (int i = 0; i < m; i++) {
        int x;
        cin >> x;
        bfs(x); // 금지 숫자들로부터 안전도 전파
    }

    int maxSafety = 0;
    for (int i = 0; i <= n; i++) {
        maxSafety = max(maxSafety, visited[i]);
    }

    cout << maxSafety - 1 << '\n'; // depth 1부터 시작했으므로 -1
}

---

코드 설명

금지된 숫자들로부터 XOR 연산으로 확산하면서 각 수에 도달하는 최소 XOR 거리를 기록합니다.

• 핵심 알고리즘: BFS + 비트 XOR 연산
• 구현 세부사항:
  • visited[i]는 i번 숫자에 도달하는 최소 거리 (안전도 + 1)
  • XOR 연산을 통해 인접한 수로 전파하며 거리 갱신
  • 가장 큰 안전도를 가진 숫자의 거리에서 1을 빼서 출력
• 시간 복잡도 분석:
  • 노드 수: 최대 N개
  • 각 노드에서 최대 log₂(N)개의 이웃 → 전체 복잡도 O(N log N)

---

결과

예시 입력:

10
1
8

예시 출력:

4

금지된 숫자로부터 가장 멀리 떨어진 숫자를 BFS로 찾아낸 뒤, 그 안전도를 출력했습니다.
BFS와 XOR의 결합으로 효율적으로 비밀번호를 제작할 수 있는 문제였습니다.
더 나은 접근 방식이 있다면 댓글로 공유해주세요!