[백준/JAVA] 20304 비밀번호 제작

https://www.acmicpc.net/problem/20304

20304번: 비밀번호 제작

 

코드

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

public class Main {
	static int n,m,answer;
	static int[] keys;
	static Queue<Integer> q = new ArrayDeque<>();
	static int[] arr = new int[1000005];

	static void init() throws IOException {
		n = rstn(); m = rstn(); keys = ra();
		Arrays.fill(arr,-1);
		for(int key : keys){
			arr[key] = 0;
			q.add(key);
		}
	}

	static int bfs(){
		while(!q.isEmpty()){
			int cur = q.poll();
			answer = Math.max(arr[cur],answer);
			for(int i=0; i<20; ++i){
				int nx = (1<<i)^cur;
				if(nx>n || arr[nx]!=-1) continue;
				arr[nx] = arr[cur]+1;
				q.add(nx);
			}
		}
		return answer;
	}

	public static void main(String[] args) throws IOException {
		init();
		System.out.println(bfs());
	}
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static void est() throws IOException {st = new StringTokenizer(br.readLine());}
	static int rstn() throws IOException {if(st==null||!st.hasMoreTokens()) est(); return Integer.parseInt(st.nextToken());}
	static int[] ra() throws IOException {return Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();}
}

 

문제풀이

bfs 태그의 문제를 풀던중 이 문제를 마주쳐 bfs로 쉽게 풀렸다. 이 문제가 어려운 난이도인 이유는 bfs+비트마스킹으로 풀린다는 자체를 쉽게 캐치할 수 없어서 그런 것 같다.

첫번째로 안전도가 0인 즉 시도 해봤던 비밀번호들을 큐에 삽입한 후 안전도가 1차이나는 숫자들을 큐에 삽입 + 안전도 갱신으로 풀 수 있다.

안전도가 1만큼 차이나는 수를 구하기 위해 (1<<i)의 시프트 연산을 수행했고,  최대범위의 log2 값인 20까지 루프를 돌려주면된다.