백준 2196번: 이진수 XOR (Java)

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

2196번: 이진수 XOR

문제

길이 B(1 ≤ B ≤ 16)인 이진수들이 E(1 ≤ E ≤ 100)개 있다. 이 이진수들을 두 개씩 선택하여 XOR연산을 하여, 어떤 이진수를 만들려고 한다. 이 과정에서 만들어지는 이진수들을 이용하여 XOR연산을 해도 되며, 같은 두 이진수를 XOR연산을 해도 된다.

만약 우리가 만들고자 하는 이진수를 만들 수 없다면, 이 이진수와 제일 가까운 이진수를 만들려고 한다. 제일 가깝다는 것은, 두 이진수들에서 서로 다른 비트의 개수가 최소인 것을 말한다. 만약 여러 개의 이진수가 제일 가까운 경우에는, XOR 연산을 가장 적게 사용하는 이진수를 출력한다. 같은 회수의 연산을 사용한다면 사전식으로 제일 앞에 오는 이진수를 출력한다.

XOR 연산자는 ^이고, 0^0=0, 0^1=1, 1^0=1, 1^1=0이다. 10110과 11101을 XOR 연산을 하면 01011이 된다.

입력

첫째 줄에 B, E가 주어진다. 다음 줄에는 우리가 만들고자 하는 이진수를 나타내는 B개의 숫자(0 또는 1)이 주어진다. 다음 E개의 줄에는 각각의 이진수들이 주어진다.

출력

첫째 줄에 사용한 XOR 연산의 회수를 출력한다. 다음 줄에는 이진수를 출력한다. 첫째 줄에 출력한 연산의 회수는 둘째 줄의 이진수를 만들기 위해 사용한 XOR 연산의 회수이다. XOR 연산은 적어도 한 번 해야 한다.

 

---

 

풀이

비트DP + BFS입니다. 주의할 점으로는, 최소 한 번은 XOR 연산을 해야한다는 점입니다.

특별할 건 없는 문제인데, Java로 푼 사람이 별로 없길래 혹시 누군가 도움을 받았으면 해서 올립니다.

 

코드

import java.io.*;
import java.util.*;
 
public class Main {
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int B = Integer.parseInt(st.nextToken());
        int E = Integer.parseInt(st.nextToken());
        int target = binaryToNum(br.readLine());
        int[] nums = new int[E];
        for (int i = 0; i < E; i++) {
            nums[i] = binaryToNum(br.readLine());
        }
        
        boolean[] visited = new boolean[1<<B];
        int[] dist = new int[1<<B];
        Arrays.fill(dist, 10000);
        
        Queue<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i < E; i++) {
            for (int j = 0; j < E; j++) {
                int cur = nums[i] ^ nums[j];
                if (visited[cur]) continue;
                visited[cur] = true;
                dist[cur] = 1;
                queue.offer(cur);
            }
        }
        
        int d = 1;
        while (!queue.isEmpty()) {
            int size = queue.size();
            d++; 
            while (size-- > 0) {
                int cur = queue.poll();
                for (int i = 0; i < E; i++) {
                    int nxt = cur ^ nums[i];
                    if (visited[nxt]) continue;
                    visited[nxt] = true;
                    dist[nxt] = d;
                    queue.offer(nxt);
                }
            }
        }
        
        // 만약 target에 도달할 수 있다면 바로 끝내기
        if (dist[target] < 10000) {
            System.out.println(dist[target]);
            System.out.println(numToBinary(target, B));
            return;
        }
        
        // 거리 차이가 작은 것 중 XOR 연산을 가장 적게하는 수 찾기
        boolean[] visited2 = new boolean[1<<B];
        visited2[target] = true;
        queue.offer(target);
        int minDist = 10000;
        int num = 0;
        while (!queue.isEmpty()) {
            int cur = queue.poll();
            for (int i = 0; i < B; i++) {
                int nxt = cur ^ (1<<i);
                if (visited2[nxt]) continue;
                visited2[nxt] = true;
                queue.offer(nxt);
                if (dist[nxt] < minDist) {
                    num = nxt;
                    minDist = dist[nxt];
                } else if (dist[nxt] == minDist) {
                    if (num > nxt) {
                        num = nxt;
                    }
                }
            }
            if (minDist < 10000) break;
        }
        System.out.println(minDist);
        System.out.println(numToBinary(num, B));
    }
    
    // 이진수를 수로
    static int binaryToNum(String num) {
        int ret = 0;
        int x = 1;
        for (int i = num.length()-1; i >= 0; i--) {
            if (num.charAt(i) == '1') ret += x;
            x *= 2;
        }
        return ret;
    }
 
    // 수를 이진수로
    static String numToBinary(int num, int digit) {
        String str = "";
        for (int i = 0; i < digit; i++) {
            if (num % 2 == 1) str = "1" + str;
            else str = "0" + str;
            num /= 2;
        }
        return str;
    }
}