문제 설명
펜윅트리를 하며 비트마스킹을 써왔던 것이 조금은 도움이 되었습니다.
이번 문제는 만들어둔 사진으로 대체하겠습니다.
아래의 과정(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);
}
}