그래프 최단 거리(BFS)

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

 

입력예시

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

 

나의 답변 

public class Main {
    static int n, m; // 정점의 개수와 간선의 개수
    static int[] ck; // 방문 여부를 체크하는 배열
    static int[] dis; // 시작 정점으로부터의 거리를 저장하는 배열
    static ArrayList<ArrayList<Integer>> graph; // 그래프를 표현하는 인접 리스트

    // BFS를 수행하는 메서드
    public void BFS(int start) {
        Queue<Integer> q = new LinkedList<>(); // 큐를 이용한 BFS
        ck[start] = 1; // 시작 정점을 방문했음을 체크
        dis[start] = 0; // 시작 정점까지의 거리는 0
        q.offer(start); // 시작 정점을 큐에 삽입
        while (!q.isEmpty()) {
            int current = q.poll(); // 큐에서 정점을 하나 꺼내옴
            for (int next : graph.get(current)) { // 해당 정점에 인접한 정점들을 순회
                if (ck[next] == 0) { // 방문하지 않은 정점일 경우
                    ck[next] = 1; // 해당 정점을 방문했음을 체크
                    dis[next] = dis[current] + 1; // 시작 정점으로부터의 거리를 갱신
                    q.offer(next); // 다음 정점을 큐에 삽입
                }
            }
        }
    }

    public static void main(String[] args) {
        Main T = new Main();
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt(); // 정점의 개수 입력
        m = sc.nextInt(); // 간선의 개수 입력
        ck = 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); // 양방향 그래프이므로 양쪽 정점에 서로를 추가
            graph.get(b).add(a);
        }
        T.BFS(1); // BFS 수행
        for (int i = 2; i <= n; i++) {
            System.out.println(i + " : " + dis[i]); // 시작 정점으로부터의 거리 출력
        }
    }
}

 

 

 

 

for 루프의 조건을 i <= n으로 설정하는 이유 : 인덱스 i가 노드를 나타내고 실제 노드 번호는 1부터 n까지이다.

따라서 graph 리스트의 크기를 n+1로 만들어야한다. 이렇게 하면 인덱스 0은 사용하지 않고, 노드 번호와 인덱스가 일치하게 된다.