Baekjoon #2479

Baekjoon #2479

1개의 풀이 · Java

문제 원문 보기 ↗

SOLUTION INFO

Java · Main.java

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

public class Main {
    public static void main(String[] args) {
        FastReader rd = new FastReader();
        int N = rd.nextInt();
        int K = rd.nextInt();

        int[] a = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            int num = 1;
            String str = rd.next();
            int total = 0;
            for (int j = K - 1; j >= 0; j--) { // 이진코드 -> int화
                int val = str.charAt(j) - '0';
                if (val == 1) {
                    total += val * num;
                }
                num *= 2;
            }
            a[i] = total;
        }

        int A = rd.nextInt();
        int B = rd.nextInt();
        Queue<Node> q = new LinkedList<>();
        q.add(new Node(a[A], A+""));
        boolean visited[] = new boolean[N + 1];
        visited[A] = true;

        String ans = "-1";
        while (!q.isEmpty()) {
            Node curr = q.poll();
            if (curr.num == a[B]) {
                ans = curr.path;
                break;
            }

            for (int i = 1; i <= N; i++) {
                if (visited[i] || a[i] == curr.num) continue;

                if (Integer.bitCount(curr.num ^ a[i]) == 1) {
                    visited[i] = true;
                    q.add(new Node(a[i], curr.path + " " + i));
                }
            }
        }

        System.out.println(ans);
    }

    private static class Node {
        int num;
        String path;

        Node(int num, String path) {
            this.num = num;
            this.path = path;
        }
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}

SOLUTION DESCRIPTION

풀이 설명

1. 비트마스킹 응용 문제로, 해밍비트가 1인 경우를 코드로 구현할 수 있다면 쉽게 문제를 해결할 수 있다. 2. 더불어, `A->B` 까지의 가장 짧은 해밍 비트 경로를 찾아야하므로, `BFS` 를 적용했다. 3. 임의의 코드에 대해, 동일한 코드가 아니며 아직 방문하지 않은 코드 가운데, 두 코드를 `XOR` 연산을 했을 때, 참인 비트의 수가 `1` 인 경우에 대해 탐색을 이어가는 방식으로 문제를 해결할 수 있다.