[BFS] 그래프의 최단거리

문제 유형

방향 그래프가 주어지고 1번 정점에서 각 정점으로 가는 최소 이동 간선수를 구하시오

필요 자료구조

1. Node와 Level을 사용한 방식

2. 인접리스트를 사용한 방식

2번 인접리스트 방식 설명

필요 자료구조

n(정점 수), m(간선 수), check 배열(중복 방지), dis배열(최단 경로 수), graph 초기화(ArrayList), Queue(BFS 알고리즘),

BFS 핵심 로직

public void BFS(int val){
	Queue<Integer> Q = new LinkedList<>();
    
	ch[val] = 1;
    dis[val] = 0;
    
    Q.offer(val);
    
    while(!Q.isEmpty()){
    	int cv = Q.poll(); // 시작 정점
        for(int nv : graph.get(cv)){
        	if(ch[nv] == 0){
            	ch[nv] = 1;
                Q.offer(nv);
                dis[nv] = dis[cv] + 1; 
            }
        }
    }
}