[자료구조] 그래프 최단거리 (BFS)

 

 

그래프 최단 거리 (BFS)

 

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

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

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

입력예제1
6 9
1 3
1 4
2 1
2 5
3 4
4 5
4 6
6 2
6 5

출력예제1
2 : 3
3 : 1
4 : 1
5 : 2
6 : 2

 

 

📌 코드 구현

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

public class Prac {

	static int n, m;
	
	static ArrayList<ArrayList<Integer>> graph;
	
	static boolean[] check;

	static int[] dis;
	
	public static void main(String[] args){
		
		Scanner sc = new Scanner(System.in);
		
		n = sc.nextInt();  // 정점 수
		m = sc.nextInt();  // 간선 수
		
		graph = new ArrayList<>();
		
		for(int i=0; i<=n; i++)
			graph.add(new ArrayList<>());
		
		check = new boolean[n+1];
		dis = new int[n+1];
		
		for(int i=0; i<m; i++) {
			int from = sc.nextInt();
			int to = sc.nextInt();
			
			graph.get(from).add(to);
		}
		
		check[1] = true;
		BFS(1);

		for(int i=2; i<=n; i++) {
			System.out.println(i+ " : " + dis[i]);
		}
		
	}

	static void BFS(int start) {
		Queue<Integer> queue = new LinkedList<>();
		check[start] = true;
		dis[start] = 0;
		queue.offer(start);
		
		while(!queue.isEmpty()) {
			int curr = queue.poll();
			
			for(int i : graph.get(curr)) {
				if(!check[i]) {
					check[i] = true;
					queue.offer(i);
					dis[i] = dis[curr]+1;
				}
			}
		}
		
	}
}

2 : 3
3 : 1
4 : 1
5 : 2
6 : 2