BFS를 이용해서 그래프 Depth 찾기

들어가기에 앞서,
앞선 BFS는 2차원 배열로 표기했는데
2차원 배열로도 표시할 수 있지만 난 주로 아래와 같은 ArrayList를 사용한다.

ArrayList<Integer> Graph[];

ArrayList를 사용하면 노드들의 관계를 다음과 같이 정의할 수 있다.

Graph[node1].add(node2);

ArrayList로 표기를 하면
조금 더 startNode와 연결된 endNode들을 가시성 있게 표시할 수 있기 때문이다.

for (int next : Graph[node] {
	System.out.println(next)
}

알고리즘 문제를 풀다보면 간혹 시작 노드에서 목표 노드까지 몇번을 타고 들어가야하는가
구하는 문제가 나온다.

[ 프로그래머스 ]가장 먼 노드
[ 백준 ] 특정한 최단 경로
[ 백준 ] 최단 경로

이런 알고리즘에서 중요한 핵심은 각 노드들의 거리를 저장할 Distance 배열 을 이용하는 것.

BFS 메서드 중 Queue에 노드를 추가하는 부분에

• Distance[next] = Distance[currentNode] + 1;

를 쓰면 시작노드에서 부터 각 노드까지 얼마나 깊이 들어가야 하는가 알 수 있다.

-  Java Code

    static ArrayList<Integer> Graph[];
    static boolean Visited[];
    static int Distance[];

    public static void main(String[] args) throws IOException {

        int[][] edge = {
                {3, 6},
                {4, 3},
                {3, 2},
                {1, 3},
                {1, 2},
                {2, 4},
                {5, 2}};

        int n = 6;

        Graph = new ArrayList[n + 1];
        Visited = new boolean[n + 1];
        Distance = new int[n + 1];

        for (int i = 1; i < Graph.length; i++) {
            Graph[i] = new ArrayList<>();
        }

        for (int i = 0; i < edge.length; i++) {
            int curr[] = edge[i];

            Graph[curr[0]].add(curr[1]);
            Graph[curr[1]].add(curr[0]);
        }

        bfs(1);

        int maxSize = 0;
        for (int i = 1; i < Distance.length; i++) {
//            System.out.println("Node[" + i + "] : " + Distance[i]);
            maxSize = Math.max(Distance[i], maxSize);
        }

        int count = 0;
        for (int i = 1; i < Distance.length; i++) {
            if (Distance[i] == maxSize) {
                count++;
            }
        }

        System.out.println(count);

    }

    static void bfs (int node) {

        Visited[node] = true;

        Queue<Integer> q = new LinkedList<>();
        q.add(node);

        while (!q.isEmpty()) {
            int curr = q.poll();

            for (int next : Graph[curr]) {
                if (Visited[next] == false) {
                    Visited[next] = true;
                    q.add(next);
                    Distance[next] = Distance[curr] + 1; // !!!!!! 이 부분 추가 !!!!!!!
                }
            }
        }
    }