그래프 최단거리(BFS)

설명

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

 

입력

첫 번째 줄에 정점의 수 N(1<=N<=20)과 간선의 수 N이 주어진다. 그 다음부터 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

 

문제 해결

 

최단 거리이므로 BFS로 해결해보자.

• 1에서 시작하기때문에 1은 0
• 3과 4 => 1 (한 번만에 갈 수 있으므로). 그리고 1,3,4는 큐에 들어간 상태이며 방문했다고 체크
• 3이 큐에서 나오고 연결된 4. 4는 이미 체크됐으므로 4에서 연결된 5,6을 체크.
• 5는 4의 값에 +1 (dis[nv] = dis[v] +1) 즉 2 그리고 큐에 들어가고 체크
• 6도 2, 큐에 들어가고 체크 ..... 이런 식으로 동작하는 코드를 구현하면 된다.

private static void BFS(int v) {
    Queue<Integer> queue = new LinkedList<>();
    distance = new int[N + 1];
    visited = new int[N + 1];

    queue.offer(v);
    distance[v] = 0; // 시작 정점 거리 0
    visited[v] = 1; // 방문 O

    while (!queue.isEmpty()) {
        int current = queue.poll();

        for (int next : List.get(current)) {
            if (visited[next] == 0) { // 아직 방문하지 않은 정점이라면
                visited[next] = 1;
                distance[next] = distance[current] + 1; // 현재 정점에서의 거리 + 1
                queue.offer(next);
            }
        }
    }
}

• 시작 정점의 거리를 0으로 설정하고, 방문 처리
• 큐에서 정점을 하나씩 꺼내면서 정점과 연결되고, 아직 방문하지 않은 정점을 큐에 추가하고 거리를 업데이트

 

최종 코드

 

import java.util.*;

public class P14_그래프최단거리_BFS {
    static int N;
    static ArrayList<ArrayList<Integer>> List;
    static int[] distance;
    static int[] visited;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        N = in.nextInt();
        int M = in.nextInt();

        List = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
            List.add(new ArrayList<>());
        }

        for (int i = 0; i < M; i++) {
            int from = in.nextInt();
            int to = in.nextInt();
            List.get(from).add(to);
        }

        BFS(1);

        for (int i = 2; i <= N; i++) { //2번 정점부터 distance 출력
            System.out.println(i + " : " + distance[i]);
        }
    }

    private static void BFS(int v) {
        Queue<Integer> queue = new LinkedList<>();
        distance = new int[N + 1];
        visited = new int[N + 1];

        queue.offer(v);
        distance[v] = 0; // 시작 정점 거리 0
        visited[v] = 1; // 방문 O

        while (!queue.isEmpty()) {
            int current = queue.poll();

            for (int next : List.get(current)) {
                if (visited[next] == 0) { // 아직 방문하지 않은 정점이라면
                    visited[next] = 1;
                    distance[next] = distance[current] + 1; // 현재 정점에서의 거리 + 1
                    queue.offer(next);
                }
            }
        }
    }
}