[BOJ] 20304 비밀번호 제작 - JAVA

1. 문제

20304번: 비밀번호 제작

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

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

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

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

---

2. 풀이

두 비밀번호의 안전거리 - 두 비밀번호의 서로 다른 자리 개수
비밀번호의 안전도 - 지금까지 로그인시도된 모든 비밀번호와의 안전거리 중 최소값
안전도가 제일 높은 비밀번호의 안전도를 구하려면 BFS를 사용하면 된다. depth가 비밀번호 i의 최솟값이다.

 

입력

1.  각 비밀번호의 안전도를 저장할 result 배열을 만든다. 타입은 int다. 

2.  방문여부 확인을 쉽게하기 위해 result를 모두 -1로 채운다. 

3.  로그인 시도된 비밀번호를 입력받으면서 result를 0으로 만들고, 큐에 넣는다.

BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(in.readLine());
int M = Integer.parseInt(in.readLine());
StringTokenizer st = new StringTokenizer(in.readLine());

int[] result = new int[N+1];
Arrays.fill(result,-1);
Queue<Integer> queue = new ArrayDeque<>();

int num, max = 0;
for(int i=0;i<M;i++){
   num = Integer.parseInt(st.nextToken());
   queue.offer(num);
   result[num] = 0;
}

 

BFS ( + 출력)

1.  큐가 빌 때까지 반복한다.

2.  첫번째 요소를 뽑아서 max값과 비교한 후 더 큰 값을 max에 저장한다.

3.  i를 0부터 19까지 반복하면서 탐색한다. 반복문의 조건을 next<=N으로 하지 않고 i<20을 하는 이유는 중간에 N보다 큰 값이 되어도 다음 값이 N보다 작을 수 있기 때문이다.

    ex) 이 예시는 모두 2진법 숫자다!

    N = 1100, num = 1011, next = 1010 -> 1001 -> 1111 -> 0011

4.  next에 현재 num과 (1<<i)을 xor한 값을 저장한다. next가 N보다 크거나 이미 방문한 적 있는 경우는 continue한다. 

5.  result[next]에 result[num]+1을 저장하고, queue에 next를 넣는다.

6.  탐색이 끝나면 max를 출력한다.

while(!queue.isEmpty()){
   num = queue.poll();
   if(max<result[num]) max = result[num];

   for(int i=0, next;i<20;i++){
      next = num^(1<<i);
      if(next > N || result[next]>-1) continue;
      result[next] = result[num]+1;
      queue.offer(next);
   }
}

System.out.println(max);

 

전체 코드

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

public class BOJ_20304_비밀번호제작 {
   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      int N = Integer.parseInt(in.readLine());
      int M = Integer.parseInt(in.readLine());
      StringTokenizer st = new StringTokenizer(in.readLine());

      int[] result = new int[N+1];
      Arrays.fill(result,-1);
      Queue<Integer> queue = new ArrayDeque<>();

      int num, max = 0;
      for(int i=0;i<M;i++){
         num = Integer.parseInt(st.nextToken());
         queue.offer(num);
         result[num] = 0;
      }

      while(!queue.isEmpty()){
         num = queue.poll();
         if(max<result[num]) max = result[num];

         for(int i=0, next;i<20;i++){
            next = num^(1<<i);
            if(next > N || result[next]>-1) continue;
            result[next] = result[num]+1;
            queue.offer(next);
         }
      }

      System.out.println(max);
   }
}

---

3. 결과

작년 2월에 한 번 풀고 오늘 한 번 더 풀었다. 음.. 아직도 어렵다.