[BaekJoon] 20304번 - 비밀번호 제작 [Java][C++]

문제 링크

---

1. 아이디어

두 수의 안전 거리는 각 수를 2진수로 나타냈을 때 서로 다른 자리의 개수로 정의됐다. 이는 두 수를 XOR 연산한 결과에서 1의 개수와 동일하다.

해당 문제는 이 XOR 연산과 BFS를 활용하면 해결할 수 있는데 특정 수에서 임의의 한 자리의 비트를 바꿀 경우 기존 수와의 안전 거리가 1이 된다는 점을 활용하면 된다. 초기 모든 비밀번호를 큐에 담은 후 방문 체크를 수행하고 이후 큐에서 하나씩 꺼내서 각 자리의 비트를 뒤집은 수를 큐에 담아주면 된다. 방문 체크를 하므로 같은 수가 다시 담기지 않으며 초기 비밀번호들에 대해 해당 로직을 수행하면 초기 비밀번호와 안전 거리가 1인 수들이 큐에 새롭게 담기게 된다. 같은 로직을 한번 더 수행하면 초기 비밀번호와 안전 거리가 2인 수들이 큐에 담기게 되며 이런 과정을 반복했을 때 큐에 더 이상 원소가 담기지 않는다면 안전 거리의 최댓값을 구할 수 있다. 레벨 BFS가 아닌 거리 배열을 활용해도 거리 배열에서 최댓값을 찾는다면 동일하게 해결할 수 있다.

핵심 로직은 특정 수와 안전 거리가 1인 수들을 찾는 것으로 특정 수를 cur이라 했을 때, cur ^ (1 << i)로 i를 0부터 증가시키며 안전 거리가 1인 다음 수들을 모두 뽑아낼 수 있다. 비밀번호의 최댓값이 1,000,000이어서 1 << 19까지만 비트를 뒤집어보면 된다.

---

2. 코드

1. 풀이 [Java]

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int n = Integer.parseInt(br.readLine());
        int m = Integer.parseInt(br.readLine());

        Queue<Integer> q = new ArrayDeque<>();
        boolean[] vis = new boolean[1 + n];

        st = new StringTokenizer(br.readLine());
        while (m-- > 0) {
            int x = Integer.parseInt(st.nextToken());
            q.offer(x);
            vis[x] = true;
        }

        int dist = 0;

        while (!q.isEmpty()) {
            int sz = q.size();

            while (sz-- > 0) {
                int cur = q.poll();

                for (int i = 0; i < 20; i++) {
                    int nxt = cur ^ (1 << i);
                    if (nxt > n || vis[nxt]) continue;

                    q.offer(nxt);
                    vis[nxt] = true;
                }
            }

            dist++;
        }

        System.out.println(dist - 1);
    }
}

2. 풀이 [C++]

#include <bits/stdc++.h>
using namespace std;

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

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

    queue<int> q;
    vector<bool> vis(1 + n);

    while (m--) {
        int x;
        cin >> x;

        q.push(x);
        vis[x] = true;
    }

    int dist = 0;

    while (!q.empty()) {
        int sz = q.size();

        while (sz--) {
            int cur = q.front();
            q.pop();

            for (int i = 0; i < 20; i++) {
                int nxt = cur ^ (1 << i);
                if (nxt > n || vis[nxt]) continue;

                q.push(nxt);
                vis[nxt] = true;
            }
        }

        dist++;
    }

    cout << dist - 1;
}

---

3. 디버깅

없음.

---

4. 참고

없음.

---