그래프 최단거리(BFS)

다음 그래프에서 1번 정점에서 각 정점으로 가는 최소 이동 간선수를 출력하세요.

입력설명

첫째 줄에는 정점의 수 N(1<=N<=20)와 간선의 수 M가 주어진다. 그 다음부터 M줄에 걸쳐 연 결정보가 주어진다.

 

출력설명

1번 정점에서 각 정점으로 가는 최소 간선수를 2번 정점부터 차례대로 출력하세요.

 

입력예제

6 9

1 3

1 4

2 1

2 5

3 4

4 5

4 6

6 2

6 5

 

출력예제

2 : 3

3 : 1

4 : 1

5 : 2

6 : 2

 

이 문제는 풀이방식이 2개이나 인접리스트로 하는게 나중에 정점이 많아지거나 2차원 배열을 사용할 때 유리해 진다.

 

첫번째 방식(Node사용)

두번째 방식(인접리스트 사용)

import java.util.*;

class Main{
	static int n, m;
	static ArrayList<ArrayList<Integer>> graph;
	static int[] ch, dis;
	public void BFS(int v) {
		Queue<Integer> queue = new LinkedList<>();
		ch[v] = 1;
		dis[v] = 0;
		queue.offer(v);
		while(!queue.isEmpty()) {
			int cv=queue.poll();
			for(int nv : graph.get(cv)) {
				if(ch[nv]==0) {
					ch[nv] = 1;
					queue.offer(nv);
					dis[nv] = dis[cv] + 1;
				}	
			}
		}
	}
	
	public static void main(String[] args) {
		Main T = new Main();
		Scanner in = new Scanner(System.in);
		// 정점의 갯수
		n=in.nextInt();
		// 간선의 갯수
		m=in.nextInt();
		// 인접리스트 초기화
		graph = new ArrayList<ArrayList<Integer>>();
		for(int i=0; i<=n; i++) {
			graph.add(new ArrayList<Integer>());
		}
		ch = new int[n+1];
		dis = new int[n+1];
		// 값 넣기
		for(int i=0; i<m; i++) {
			int a = in.nextInt();
			int b = in.nextInt();
			graph.get(a).add(b);
		}
		T.BFS(1);
		for(int i=2; i<=n; i++) {
			System.out.println(i+" : "+dis[i]);
		}
	}
}