백준 20304 비밀번호 제작 풀이 python, java

문제로이동

---

목차

 

---

---

문제 설명

펜윅트리를 하며 비트마스킹을 써왔던 것이 조금은 도움이 되었습니다.

이번 문제는 만들어둔 사진으로 대체하겠습니다.

 

아래의 과정(BFS)을 반복적으로 거치고 나면 가장 처음에 입력된 값을 기준으로 1의 거리를 가진 간선들이 연결되어 있습니다.

 

---

소스 코드

Python

from collections import deque
import sys
input = sys.stdin.readline
MIN = -10e9
N = int(input())
M = int(input())
arr = [MIN]*1000001
dq = deque()
xs = list(map(int,input().split()))
for x in xs:
    arr[x] = 0
    dq.append(x)
maxnum = 0
while dq:
    x = dq.popleft()
    for i in range(20):
        nx = x^ (1<<i)
        if nx>N or arr[nx]!= -10e9:
            continue
        dq.append(nx)
        arr[nx]=arr[x]+1
        maxnum = max(arr[nx],maxnum)
print(maxnum)

---

Java8

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

public class Main {
	static StringBuilder sb = new StringBuilder();
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static int answer;
	public static void main(String[] args) throws IOException {
		int N = Integer.parseInt(br.readLine());//기본 입력
		int M = Integer.parseInt(br.readLine());
		Deque<Integer> dq = new ArrayDeque<Integer>();
		int arr[] = new int[1000001];//최대초기화
		Arrays.fill(arr, Integer.MIN_VALUE);
		st = new StringTokenizer(br.readLine());
		for(int i=1;i<=M;i++) {
			int x =Integer.parseInt(st.nextToken()); 
			arr[x] = 0;
			dq.offerLast(x);
		}//M의 범위 1<=M
		while(!dq.isEmpty()) {
			int x = dq.pollFirst();
			for(int i =0;i<20;i++){				
				int nx = x^(1<<i);
				if(nx>N||arr[nx]!=Integer.MIN_VALUE)continue;
				arr[nx] = arr[x]+1;
				dq.offerLast(nx);
				answer = Math.max(answer, arr[nx]);
			}
		}		
		System.out.println(answer);
	}
}