[알고리즘]Graph - 그래프 최단거리(BFS)

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

 

 

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	static int n, m, answer = 0;
	static int[] ch, dis; 
	static ArrayList<ArrayList<Integer>> graph;
	
	public static void BFS(int v) {
		Queue<Integer> queue = new LinkedList<>();
		ch[v] = 1;
		dis[v] = 0; // 1에서 1까지 거리는 0
		queue.offer(v);
		
		while (!queue.isEmpty()) {
			int cv = queue.poll(); // current vertex
			for (int nv : graph.get(cv)) {
				if (ch[nv]==0) {
					ch[nv] = 1;
					queue.offer(nv);
					dis[nv] = dis[cv] + 1; // 거리 + 1
				}
			}
		}
	}

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		n = scanner.nextInt(); // 정점의 수
		m = scanner.nextInt(); // 간선의 수
		ch =  new int[n+1]; // 방문한 정점
		dis =  new int[n+1]; // 최단거리
		graph = new ArrayList<ArrayList<Integer>>(); // 인접리스트
		for (int i=0; i<=n; i++) {
			graph.add(new ArrayList<Integer>()); // 초기화
		}
		for (int i=0; i<m; i++) {
			int a = scanner.nextInt();
			int b = scanner.nextInt();
			graph.get(a).add(b); // 단방향 연결
		}
		BFS(1);
		for (int i=2; i<=n; i++) {
			System.out.println(i + " : " + dis[i]);
		}
	}

}

---

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