[BFS] 2261 : 경로찾기

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 targetNode, resultNode = null;
    int n , k, startPoint, endPoint;
    int[] binary;
    boolean[] check;
    LinkedList<Node> q = new LinkedList<Node>();
    
    public void input(){
        n = sc.nextInt();
        k = sc.nextInt();
        binary = new int[n];
        check = new boolean[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) {
            targetNode = q.poll();
            if(targetNode == null) return;
            check[targetNode.numNode] = true;            
            for (int j = 0; j < n; j++) {
                if (check[j] || !getHamingDistance(binary[targetNode.numNode],binary[j])) continue;
                q.offer(new Node(j, targetNode));
                if (j == endPoint) {
                    resultNode = new Node(j, targetNode);
                    return;
                }
            }
        }
    }
    public boolean getHamingDistance(int position, int target){
        target = position ^ target;
        int count = 0;
        while(target > 0){
            if(target%2 == 1) if(count == 0) count++; else return false;
            target = target / 2;
        }
        return (count == 1) ? true : false;
    }
    public void display(){
        if(resultNode == null){
            System.out.println(-1);
            return;
        }
        LinkedList<Integer> flow = new LinkedList<Integer>();
        do{ flow.push(resultNode.numNode+1); }while((resultNode = resultNode.before) != null);
        while(flow.size() > 0) System.out.print(flow.pop() + " ");
        return;
    }
}

나를 힘들게 했던 BFS문제 중 하나. 경로 찾기 문제이다.

이 문제에서의 핵심과 그것을 해결방법은 아래와 같다.

1. Flow  Route를 어떤 원리로 저장하며 어떻게 출력할 것인가.

 -> 경우의 수 연결을 Tree형식으로 구현하여 목표 치를 달성했을때 상위 노드로 올라가능 방식으로 경로를 추적한다.

2. 어떻게하면 재 계산과 메모리 사용량을 고려하여 최적의 알고리즘을 도출할 수 있는가.

 -> Map을 만들지 않고 경우의 수를 연결할 때 노드방식으로 reference로 연결하여 사용하지 않는공간이 없게끔 만든다. 노드가 적을 경우에는 비효율적이긴하지만 결과로 가는길이 빠를 수록 노드가 많을 수록 유리하다.

3. 해당 경우의 수의 재사용 가능성은 있는가. 재 사용했을 때 그 경우는 최선이 될 수 있는가.

 -> 해당 경우의 수가 상위 Level(Deep)에서의 경우의 수에서 이미 사용된 것이라면 구지 사용할 필요가 없다. 왜냐하면 상위 경우의 수에서의 그 경우가 하위에서 결과를 도출했다면 그것이 최선이기 때문에 해당 경우의 수의 재사용 가능성을 고려해야하한다. 하지만 일부 문제에서 해당 경우의 수를 계속해서 사용하는 경우에는 (좋은 수열 같은 계속 사용 경우) 다른 알고리즘으로 효율성을 개선해야한다.

-----------------------------------------------------------------------------------

위 알고리즘의 사용 방법은 

 flow Map이라는 서로의 경우에서의 배열을 만들어도 되지만 구지 그럴 필요없지 결과가 나오는 순간 함수를 종료하고 나무 뿌리 끝에서 나무 기둥을 올라가는 것 같이 노드를 만들어 마지막 노드부터 올라간다. 배열보다 메모리를 효과적으로 사용할 수 있는 이유는 만약 1-2를 연결하려고 하는데 1-2가 바로 연결되어 있다면 flow Map 배열일경우에는 1-100번까지 있다고 가정하에 

중간에 개념을 잘못 잡아 위 3번을 고려하지 않고 모든 경우의 수의 재사용 가능성은 ON으로 하여