[JAVA] 알고리즘 : 그래프 최단거리(BFS)

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main{
    static int n, m;
    static ArrayList<ArrayList<Integer>> graph; // Integer를 저장하는 ArrayList를 저장하는 ArrayList
    static int[] ch, dis;
    public void BFS(int v){
        Queue<Integer> queue = new LinkedList<>();
        ch[v]=1; // 체크배열 체크
        dis[v]=0; // 출발점 0으로
        queue.offer(v);
        while(!queue.isEmpty()){
            int cv=queue.poll();
            for(int nv : graph.get(cv)) {// cv에서 갈수있는 정점들
                if(ch[nv]==0) { // 방문 안했다면
                    ch[nv]=1; // 방문으로 체크
                    queue.offer(nv);
                    dis[nv]=dis[cv]+1; // 그 전 노드의 최단거리 +1
                }
            }
        }
    }
    public static void main(String[] args) {
        Main T = new Main();
        Scanner kb = new Scanner(System.in);
        n=kb.nextInt();
        m=kb.nextInt();
        graph = new ArrayList<ArrayList<Integer>>();
        for(int i=0; i<=n; i++){
            graph.add(new ArrayList<Integer>()); // 정수를 저장할 수 있는 ArrayList 객체 생성
        }
        ch=new int[n+1];
        dis=new int[n+1];
        for(int i=0; i<m; i++){
            int a = kb.nextInt();
            int b = kb.nextInt();
            graph.get(a).add(b); // a번째 ArrayList에 b추가
        }
        T.BFS(1); // 1번 정점부터 시작
        for(int i=2; i<=n; i++){
            System.out.println(i+" : "+dis[i]);
        }
    }
}

 

 

 

dis 배열

1	2	3	4	5	6
0	3	1	1	2	2

 

 

 

 

n개의 ArrayList를 만들고 시작 정점번째의 ArrayList에 도착 정점들을 추가한다. 

BFS(정점)을 호출하여 해당 정점을 큐에 넣고 그 정점에서 갈 수 있는 정점들을 for문으로 돌며 방문을 안했다면

그 전 지점 노드의 dis배열 값, 즉 거리에서 +1을 하며 거리를 계산한다.