(20304) 비밀번호 제작 (Java)

문제

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

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

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

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

입력

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

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

셋째 줄에는 로그인 시도에 사용된 비밀번호 값인 정수
$p_1, p_2, \cdots, p_M$이 주어진다. ($0 \leq p_i \leq N$)

출력

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

예제 입력 1

10
2
3 4

예제 출력 1

2
비밀번호를 $8$ 또는 $9$로 설정했을 때 $K=2$로 최대이다.

출처

University > 서강대학교 > 2020 Sogang Programming Contest > Master F번

University > 서강대학교 > 2020 Sogang Programming Contest > Open N번

문제를 검수한 사람: gumgood, ho94949, jhnah917, kipa00, pichulia, rhs0266, shiftpsh, sogangcse, woonikim
문제를 만든 사람: mic1021

알고리즘 분류

그래프 이론
그래프 탐색
너비 우선 탐색
비트마스킹

Solution

import java.io.*;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BOJ20304 {
    public static int n, m;
    public static int[] safeDis;
    public static Queue<Integer> q;

    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());

        // 안전거리 초기화
        safeDis = new int[1000001];
        Arrays.fill(safeDis, Integer.MIN_VALUE);

        // 해커가 시도한 비밀번호는 안전거리 0으로 세팅하고 큐에 담는다.
        q = new LinkedList<Integer>();
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i < m; i++) {
            int p = Integer.parseInt(st.nextToken());
            q.offer(p);
            safeDis[p] = 0;
        }

        bw.write(String.valueOf(findSafeDis()));
        bw.flush();
        bw.close();
        br.close();
    }

    public static int findSafeDis() {
        int maxSafeDis = 0;

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

            // n의 최댓값인 1,000,000은 2진법으로 20자리이므로, 0 ~ 19까지 확인한다.
            for(int i = 0; i < 20; i++) {
                int nx = cur^(1<<i);

                // 비밀번호의 최댓값을 초과하거나, 이미 안전거리 계산을 마친 비밀번호인 경우 skip
                if(nx > n || (safeDis[nx] != Integer.MIN_VALUE)) continue;

                q.offer(nx);
                safeDis[nx] = safeDis[cur] + 1;
                maxSafeDis = Math.max(maxSafeDis, safeDis[nx]);
            }
        }

        return maxSafeDis;
    }
}

Feedback

비트마스킹의 개념에 대해 처음 알았다. 정수를 2진법으로 표현하여 OR, AND, XOR, Shift 등의 연산을 수행할 수 있게 해준다.

해커가 시도한 비밀번호와의 안전거리를 찾는 것이 목적이므로, 해커가 시도한 비밀번호들을 초기 큐에 넣어둔다. 그리고 최초 비교 대상이 될 값을 1 (0001)로 잡아 비트마스킹으로 left shift를 해주면서 안전거리를 +1 씩 해나간다.

예를 들어 3 (0011)과 1 (0001)의 XOR 연산을 하여 나온 수는 3과 1의 갯수가 1개만 차이나므로 안전거리 1을 갖게된다.
3 (0011) XOR 1 (0001) > 2 (0010)
3 (0011) XOR 2 (0010) > 1 (0001)
3 (0011) XOR 4 (0100) > 7 (0111)
3 (0011) XOR 8 (1000) > 11 (1011)
이런식으로 3 과 XOR 연산을 할 값은 1을 좌측으로 1칸씩 shift 해가며 선정한다. 이렇게 한 싸이클을 돌고 나면 3과 안전거리가 1인 비밀번호들을 찾을 수 있다.

이제 위에서 구한 3과 안전거리가 1만큼 차이나는 비밀번호들을 대상으로 똑같은 과정을 반복한다.
2 (0010) XOR 1 (0001) > 3 (0011)
2 (0010) XOR 2 (0010) > 1 (0001)
2 (0010) XOR 4 (0100) > 6 (0110)
이렇게 되면 이미 안전거리가 0으로 세팅되어있는 3, 이전 과정에서 안전거리가 1로 세팅되어있는 1은 큐에 다시 담지 않고 skip, 처음 나온 6은 최초 시도 비밀번호인 3과 안전거리가 1 + 1로 총 2만큼 차이나게 된다.
(물론 문제의 테스트케이스에서는 해커가 시도한 비밀번호가 3뿐만 아니라 4도 있기때문에 4에 대해 탐색을 진행할 때 6은 4와 안전거리가 1이므로 이미 safeDis 배열에 1로 세팅되어있을 것이긴하다. 하지만 예를 든 것은 해커가 비밀번호를 3만 시도하였을 경우이므로 그렇게 이해하자.)