[ 백준 20304 ] 비밀번호 제작

1. 문제

20304번: 비밀번호 제작

 

2. 풀이

결과적으로 어떤 답을 만들어내야 하는가가 다소 헷갈릴 수 있는 문제의 유형이라 생각한다. 그 중 먼저 문제의 핵심인 안전거리와 안전도를 판단하는 방법을 알아본다.

 

2.1 안전거리와 안전도

3, 4 두 가지의 비밀번호가 입력된 적 있을 때, 2라는 비밀번호를 설정했을 때의 안전거리를 알아보자. 먼저 2, 3, 4를 이진수로 변환하면 아래와 같다.

• 3: 0011
• 4: 0100
• 2: 0010

(2,3)의 경우 서로다른 비트가 한 개이기 때문에 안전거리는 1, (2,4)의 경우 두 개가 다르기 때문에 안전거리는 2다. 하지만, 안전도는 둘 중 작은 값인 1이 안전도가 된다. 즉, 입력 받은 모든 비밀번호와 새 비밀번호의 안전거리 중 가장 작은 값이 안전도가 된다.

2.2 풀이 방법 유추

여기서 우리는 이 문제를 조금 더 추상화할 수가 있다. 입력받은 적 있는 비밀번호를 그래프에서의 시작 노드라고 보고, 새로 설정할 비밀번호를 도착 노드라고 본다면 다음과 같은 그래프를 만들 수 있다. 비밀번호를 1 ~ 7(3bit)까지만 입력 가능하다고 가정하자.

시작노드를 제외한 모든 노드는 최소 1 안전거리를 통해 도달할 수 있게 되고, 해당 값이 최대값이므로 문제의 정답인 안전도는 1이 된다. 즉, 시작노드들로부터 BFS로 하나씩 뻗어나가면서 가장 길게 뻗어나갈 수 있는 거리를 탐색하면 되는 문제였다.

 

그럼 이진수에서 비트를 하나씩만 변경해서 어떻게 이동할 수 있을까?

 

2.3 비트마스크

XOR 연산을 사용하면 가볍게 해결할 수 있다. 앞서 예시로 들었던 3을 통해 살펴보자.

• 3 : 0011
• 3 ^ (1 << 0) : 0011 ^ 0001 = 0010
• 3 ^ (1 << 1) : 0011 ^ 0010 = 0001
• 3 ^ (1 << 2) : 0011 ^ 0100 = 0111
• ...

1을 왼쪽 시프트 연산을 통해서 XOR 연산을 수행한다면 한 자리씩만 바꿔가며 숫자를 만들어낼 수가 있다! 비트마스크 만세!

 

그럼 이제 BFS와 비트마스크 연산을 통해 다음 노드들을 만들어가며 탐색할 수 있으므로 구현만 하면 된다.

3. 소스코드

public class Main {

    static int N, M;
    static int[] visit;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());

        visit = new int[N + 1];
        Arrays.fill(visit, -1);

        Queue<Integer> q = new LinkedList<>();

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < M; i++) {
            int n = Integer.parseInt(st.nextToken());
            q.add(n);
            visit[n] = 0;
        }

        bw.write(bfs(q) + "");

        bw.flush();
        bw.close();
        br.close();
    }

    static int bfs(Queue<Integer> q) {
        int ans = 0;

        while (!q.isEmpty()) {
            int now = q.poll();

            for (int i = 0; i < 20; i++) {
                int next = now ^ (1 << i);
                if (N < next || visit[next] != -1) continue;
                visit[next] = visit[now] + 1;
                q.add(next);
                ans = Math.max(ans, visit[next]);
            }
        }

        return ans;
    }
}

 

[Platinum 5] 20304번 비밀번호 제작 by kwanik-kor · Pull Request #25 · kwanik-kor/BOJ