그래프 최단거리 구하기 (인접리스트 사용)

1. BFS를 이용한다. (노드에 도달하는 레벨을 체크)

2. dis 배열을 사용하여 노드에 접근했을 때의 누적 거리를 체크한다.

class Main {

	static int n,m;		
	static int [] ch;//중복 방지용 : 한번 지나간 정점은 다시 찾지 않는다.(무한루프 방지)
	static int [] dis;
	static ArrayList<ArrayList<Integer>> graph; // 인접 리스트 생성.
	static int answer;

	public void BFS ( int v) {
		Queue<Integer> Q = new LinkedList<>();
		
		//초기화
		ch[v] = 1;
		dis[v] = 0;
		Q.offer(v);
		
		while ( !Q.isEmpty()) {
			
			int len = Q.size();
			for ( int i =0 ; i < len ; i++) {
				int cv = Q.poll();
				System.out.println("cv : "+cv );
				for ( int nv : graph.get(cv) ) {
					if( ch[nv] == 0) { //중복하여 순회하지 않음.
						ch[nv]=1; 
						dis[nv] = dis[cv] + 1;// 중요 : 정점을 이동해가면서 거리를 누적.						
						Q.offer(nv);
					}
				}
				
				
			}
			
		}
		
	}
	
	
	public static void main(String args[]) throws Exception {
		Main M = new Main();
		Scanner in = new Scanner(System.in);
		n = in.nextInt();
		m = in.nextInt();
		ch = new int[n+1];
		dis = new int[n+1];
		
		graph = new ArrayList<>();
		for ( int i = 0 ; i <= n ; i++) {
			graph.add(new ArrayList<Integer>());
		}
		
		for ( int i = 0 ; i < m ; i++) {
			graph.get(in.nextInt()).add(in.nextInt());
		}
		
		//인접리스트 출력
		int idx= 0;
		
		for ( ArrayList<Integer> a : graph) {	
			System.out.print("[ " +idx+ "]");
			for (int e : a) {
				System.out.print(e + " ");	
			}
			System.out.println();
			idx++;
		}
		
		//1번 정점에서 출발
		ch[1]=1;
		M.BFS(1);
		
		for( int i = 1 ; i <=n ; ++i)
			System.out.print(dis[i] + " ");
		System.out.println();
	}
}

ex)
input
6 9
1 3
1 4
2 1
2 5
3 4
4 5
4 6
6 2 
6 5
output
[ 0]
[ 1]3 4 
[ 2]1 5 
[ 3]4 
[ 4]5 6 
[ 5]
[ 6]2 5 
cv : 1
update dis to 1
update dis to 1
cv : 3
cv : 4
update dis to 2
update dis to 2
cv : 5
cv : 6
update dis to 3
cv : 2
0 3 1 1 2 2