문제 // 자료구조 // 트리(Tree) // 연결확인 // toJava

/**
 * [노드사이의 경로]
 *  "방향그래프"가 주어졌을때, 두 노드 사이에 경로가 존재하는지 확인하는 알고리즘을 작성
 *
 * [풀이]
 *  => 시작부터 끝까지 너비우선탐색 & 깊이우선탐색으로 확인가능
 *  => 양방향탐색을 진행해서 만나는 점이 있다면 확인이 가능
 * */

public class Q01 {

    /* MyGraph */
    public static class Graph {
        public Node[] getNodes() {
            return null;
        }
    }

    /* Node */
    public static class Node {
        State state;
        public Node[] getAdjacent() {
            return null;
        }
    }

    /*State */
    enum State { Unvisited, Visited, Visiting }

    /* search(너비우선탐색) */
    public static boolean search(Graph g, Node start, Node end) {
        if( start == end ) return true;

        // == 초기화 ==
        for(Node u : g.getNodes()) {
            u.state = State.Unvisited;
        }

        // == 너비우선탐색(BFS) - queue ==
        LinkedList q = new LinkedList();
        start.state = State.Visiting;
        q.add(start);
        Node u;
        while(!q.isEmpty()) {
            u = (Node) q.removeFirst();

            if(u != null) {
                for( Node v : u.getAdjacent()) {
                    if(v.state == State.Unvisited) {
                        if(v == end) {
                            return true;
                        } else {
                            v.state = State.Visiting;
                            q.add(v);
                        }
                    }
                }
                u.state = State.Visited;
            }
        }
        return false;
    }

}