BFS로 Graph 노드 레벨 구하기 / 최소 거리 구하기

풀이 
> distance 배열을 만들어서 노드의 레벨을 저장해두고, 다음 번 방문시 기존 레벨이 저장되어있으면 레벨 값을 바꾸지 않는다.

코드

import java.util.*;

/**
 * 그래프에서 노드간 최소단거리 탐색 / 노드별 레벨 구하기
 * 간선에 가중치 없음 (크루스칼 아님)
 *
 * 출발은 항상 1번
 * 출발지 1번을 제외한 나머지 노드로 가는 최소값을 가진 배열 return
 *
 */
public class graphSrch {

    public void solution(int[] n, int[][] edges) {
        boolean[] ck = new boolean[n.length];
        List[] link = new List[n.length];
        int[] distance = new int[n.length];
        Stack<Integer> st = new Stack<Integer>();
        Queue<Integer> q = new LinkedList<>();

        int cur = 0;
        int end = 0;
        int cnt = 0;  //레벨

        //거리 초기화
        for(int i =1; i<distance.length; i++){
            distance[i] = n.length;
        }
        for (int i = 1; i < link.length; i++) {
            link[i] = new ArrayList<Integer>();
        }

        //간선 연결 작업
        for (int i = 0; i < edges.length; i++) {
            link[edges[i][0]].add(edges[i][1]);
            link[edges[i][1]].add(edges[i][0]);
        }
        
        //BFS 풀이
        ck = new boolean[n.length];
        cnt = 0;
        //end = i;
        //출발은 항상 1
        q.add(n[1]);
        while(!q.isEmpty()){
            cur = q.peek();
            q.poll();
            if(cnt<distance[cur]){
                distance[cur] = cnt;
            }

            //노드 방문하지 않은 경우 
            if(!ck[cur]){
                //방문 체크
                System.out.println("방문노드 : "+cur+" 현재 level :"+cnt);
                ck[cur] = true;
                //방문지점에서 갈 수 있는 다음 level add
                for(int j=0; j<link[cur].size(); j++){
                    cnt = distance[cur];

                    if(!ck[(int)link[cur].get(j)]){
                        //다음 방문할 노드기 떄문에, 거리는 현재 거리+1, 다음 방문지가 현재 거리보다 큰 경우만 변경함
                        if((cnt+1)<distance[(int)link[cur].get(j)]){
                            distance[(int)link[cur].get(j)] = cnt+1;
                        }
                        System.out.println("next = "+link[cur].get(j));
                        q.add((int)link[cur].get(j));
                    }

                }
                cnt++; // 레벨 증가
            }
        }

        System.out.println(end+"방문 최솟값 : "+cnt);


        for(int i=1; i<distance.length; i++){
            System.out.println(i +" = "+ distance[i]);
        }
    }


    public static void main(String[] args) {
        graphSrch tc = new graphSrch();

        int[] n = {0,1,2,3,4,5,6};
       // int[][] edges = {{1,3},{1,4},{2,1},{2,5},{3,4},{4,5},{4,6},{6,5},{6,2}};
        int[][] edges = {{1,2},{1,4},{1,6},{2,4},{2,5},{4,5},{5,6},{5,2},{6,3}};

        tc.solution(n,edges);
    }

}