강승현입니다
article thumbnail
반응형

문제로이동


목차

     



    문제 설명

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

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

     

    아래의 과정(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);
    	}
    }
    반응형
    profile

    강승현입니다

    @CODe_

    포스팅에 대한 피드백을 환영합니다!
    피드백 작성자를 존중하며, 함께 공유하고 성장할 수 있는 기회가 되기를 기대합니다.의견이나 조언이 있다면 언제든지 자유롭게 남겨주세요!

    article prev thumbnail

    다음 글

    백준 6497 전력난 java

    2021.03.27

    article next thumbnail
    profile on loading

    Loading...