백준 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≤N≤1000000)

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

셋째 줄에는 로그인 시도에 사용된 비밀번호 값인 정수 p1,p2,⋯,pM이 주어진다. (0≤pi≤N)

 

출력

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

 

---

 

내 시도

모종의 이유로 풀게 된 문제. 나는 풀지 못했다.

1. 0부터 N까지 하나하나 숫자마다 안전 거리를 재는 방법: O(NMlogN) 풀이라 문제 범위의 M, N에서는 무조건 시간초과가 뜬다.
2. 왠지 DP가 될 거 같다고 생각해서 한 20분 정도 생각해보았다... 안된다.

 

풀이

모 선생님께서 알려주신 환상적인 풀이이다. 

기본적으로 BFS로 푼다: 처음에 주어진 M개의 값을 queue에 넣는다. 이후 'queue에 있는 값과 한자리만 다른 값'을 계산하여, 해당 값이 N 이하이며 방문하지 않았다면 queue에 넣어준다. BFS에서 깊이를 재는 방법으로 깊이를 재준 후, 해당 값을 출력하면 된다.

 

배울 점

'깊이, 거리를 잴 때 BFS를 활용할 수 있다'를 머리 속에 넣고 있어야겠다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int M = Integer.parseInt(br.readLine());
		
		boolean[] visited = new boolean[N+1];
		Queue<Integer> queue = new ArrayDeque<Integer>();
		int depth = 0;
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < M; i++) {
			int temp = Integer.parseInt(st.nextToken());
			queue.offer(temp);
			visited[temp] = true;
		}

		while (!queue.isEmpty()) {
			int size = queue.size();
			depth++;
			while(size-- > 0) {
				int temp = queue.poll();
				// queue에서 빼준 값과 한 자리만 차이나는 값 찾기
				int x = 1;
				while (x <= N) {
					if ((x^temp) <= N && !visited[x^temp]) {
						visited[x^temp] = true;
						queue.offer(x^temp);
					}
					x =  x<<1;
				}
			}
		}
		System.out.println(depth-1); // 1 빼야함
	}

}