백준 20304: 비밀번호 제작

문제 요약

서버 관리자 계정의 비밀번호로는 $0$ 이상 $N$ 이하의 정수 중 하나를 사용할 수 있다.

두 비밀번호의 안전 거리는 이진법으로 표현한 두 비밀번호의 서로 다른 자리의 개수로 정의한다.

어떤 비밀번호의 안전도는 지금까지 로그인 시도에 사용된 모든 비밀번호와의 안전 거리 중 최솟값으로 정의한다.

이때, 안전도가 제일 높은 비밀번호의 안전도를 구하여라.

문제 분류

• 그래프 이론
• 그래프 탐색
• BFS
• 비트마스킹

문제 풀이

사실 이 문제는 그래프로 변환할 수 있다. 각 정점은 비밀번호이고, 정점에서 한 개의 비트만 바꾸어 안전거리가 1인 다른 정점을 방문할 수 있다.
여기서, m개의 정점들에 대해 multi-source bfs를 수행하면, 최소의 안전도를 구할 수 있다.

풀이 코드

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

public class Main {
	static boolean visited[];
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int res = -1, qsize, t, i, temp;
		int n = Integer.parseInt(br.readLine());
		int m = Integer.parseInt(br.readLine());
		Queue<Integer> q = new ArrayDeque<>();
		visited = new boolean[n + 1];
		st = new StringTokenizer(br.readLine());
		for(i = 0; i < m; i++) {
			t = Integer.parseInt(st.nextToken());
			visited[t] = true;
			q.offer(t);
		}		
		
		while(!q.isEmpty()) {
			qsize = q.size();
			while(qsize-- > 0) {
				t = q.poll();
				for(i = 0; i < 32; i++) {
					temp = t ^ (1 << i);
                    if((1 << i) > n) break;
					if(temp > n || temp < 0) continue;
					if(!visited[temp]) {
						visited[temp] = true;
						q.offer(temp);
					}
				}
			}
			res++;
		}
		System.out.println(res);
	}
}