[BFS] 그래프 최단 거리 .java

문제 

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

 

입력

첫째 줄에는 정점의 수 N(1<=N<=20) 와 간선의 수 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

 

내 풀이

최단 거리 => BFS

1번 정점에서 몇 번만에 갈 수 있는지 -> 이 횟수의 최솟값 구하기

 

 

 

인접리스트로 구현 및 1번 정점에서 각 인덱스 정점까지의 최소 거리를 저장하는 dis 배열 이용

 

 

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 ArrayList<ArrayList<Integer>> graph;
    static int[] ch;//방문배열
    static int[] dis;

    public static void bfs(int v) {
        Queue<Integer> q = new LinkedList<>();
        ch[v] = 1;//방문처리
        dis[v] = 0;//처음 값 0
        q.offer(v);//큐에 넣기

        while(!q.isEmpty()) {
            int cur = q.poll();//큐에서 하나 꺼내서
            for(int next : graph.get(cur)) {//연결된 인접리스트 순회
                if(ch[next] == 0) {//방문 안했다면
                    ch[next] = 1;//방문
                    q.offer(next);//큐에 추가
                    dis[next] = dis[cur] + 1;//현재 정점에서 한번 더 감
                }
            }
        }

    }

    public static void main(String[] args) {

        Main T = new Main();
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.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 = sc.nextInt();
            int b = sc.nextInt();

            graph.get(a).add(b);
        }
        bfs(1);


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


    }

}