ㅇㅇ

 
import java.util.LinkedList;
import java.util.Scanner;
 
public class Main {
    class Node {
        public Node (int numNode, Node node ){
            this.numNode = numNode;
            this.before = node;
        }
        int numNode;
        Node before;
    }
    public static void main(String[] args) {
        Main n = new Main();
        n.input();
        n.hamingRoute();
        n.display();
    }
    Scanner sc = new Scanner(System.in);
    Node find = null;
    int n , k, startPoint, endPoint, qPointer = 0;
    int[] binary = new int[n];
    boolean[] check;
    LinkedList<Node> q = new LinkedList<Node>();
    
    public void input(){
        n = sc.nextInt();
        k = sc.nextInt();
        binary = new int[n];
        for(int i = 0 ; i < n ; i ++){
            binary[i] = Integer.parseInt(sc.next(), 2);
        }
        startPoint = sc.nextInt()-1;
        endPoint = sc.nextInt()-1;
        q.offer(new Node(startPoint, null));
        return;
    }
    
    
    public void hamingRoute(){
        while (true) {
            check = new boolean[n];
            Node targetNode = q.get(qPointer);
            Node temp = targetNode;
            while ((temp = temp.before) != null) check[temp.numNode] = true;
            check[targetNode.numNode] = true;
            for (int j = 0; j < n; j++) {
                if (check[j]) continue;
                if (getHamingDistance(binary[targetNode.numNode], binary[j])) {
                    q.offer(new Node(j, targetNode));
                    if (j == endPoint) {
                        find = new Node(j, targetNode);
                        return;
                    }
                }
            }
            qPointer++;
        }
    } 
    public boolean getHamingDistance(int position, int target){
        target = position ^ target;
        int count = 0;
        while(target > 0){
            if(target%2 == 1) count++;
            target = target / 2;
        }
        return (count == 1) ? true : false;
    }
    public void display(){
        LinkedList<Integer> flow = new LinkedList<Integer>();
        do{ flow.push(find.numNode+1); }while((find = find.before) != null);
        while(flow.size() > 0) System.out.print(flow.pop() + " ");
        return;
    }
}

BFS 문제 풀이중입니다.