그래프에서 최단거리 구하기 BFS

문제 제시

• 보통 이런 문제에서 간선의 수는 도로의 갯수, 도로 1개당 이동시간 몇 분 이런식으로 나온다
• 1번 도시에서 각 도시까지 가는 최소 이동 시간을 구하시오
  • 1번 도시에서 3번, 4번 도시까지 최소 이동 시간은 1분
• 첫째 줄에는 도시의 수 N(1≤N<20) 와 도로 M 의 갯수가 주어진다. 그 후 M 번에 걸쳐 연결 정보가 주어진다.
  • 1번 도시에서는 3번과 4번 도시로 밖에 가지 못한다

BFS 로 접근하기

• 문제의 기본 접근법은 이전에 공부했던 인접 리스트 방식이다.
• ArrayList 로 n번에서 이동할 수 있는 번호를 넣어둔 후 추가로 n번에서 m 까지 이동하는데 걸리는 거리 dis 배열을 만들어서 거리를 계산한다.
  • 예를들어 1번에서 이동 할 수 있는 번호는 3, 4 번이다. 또한 3, 4 번까지 거리는 1 임으로 dis[3] = 1 && dis[4] = 1 이 된다. dis[6] = 2 가 된다
  • 즉 v - nv 로 이어지는 그래프에 대해서, dis[nv] = dis[v] +1 이 된다.

package BFS;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class BFS_dis {

    static int n, m;

    static ArrayList<ArrayList<Integer>> graph;

    // 해당 도시를 지났는지(탐색했는지) 체크하기 위한 체크배열
    // 해당 도시를 지났다면 ch 배열에 1이 들어감
    static int[] ch;

    // 1번 도시로부터 n 번 도시까지 거리를 저장하기 위한 dis 배열
    static int[] dis;

    // v 는 도시의 번호
    public void dis(int v){
        // Queue 생성 -> 해당 queue 는 LinkedList 를 담음
        // Linklist 인 이유는 도시와 도시가 연결 linked 되어 있기 때문!!
        Queue<Integer> queue = new LinkedList<Integer>();

        // v 번째를 지났다면 ch 배열의 v 번째 인덱스에 1 이 들어감
        ch[v] = 1;

        // v 번째에서 v 번째 까지 거리는 당연 0 -> 자기 자신으로의 거리
        dis[v] = 0;

        // queue 에 v 를 넣기
        queue.add(v);

        // queue 가 비어있지 않다면 ->
       while(!queue.isEmpty()){
           // currentValue 는 현재 지점(도시) 로 queue 에 저장된 값을 하나 꺼내옴
            int cv = queue.poll();
            System.out.println("cv : "+cv);
            // graph 는 Integer 를 담은 ArrayList 를 저장한 ArrayList 로
           // graph.get(1) 이면 graph 의 인덱스 1번에 저장된 ArrayList 를 불러옴
            for(int nv : graph.get(cv)){
                if(ch[nv]==0){
                    System.out.println("nv : "+nv);
                    // nv 에 방문했으면 1 로 체크
                    ch[nv] = 1;

                    // queue 에 nv 를 넣기기
                   queue.offer(nv);

                    // nv 로의 거리는 바로 이전 값 cv까지 거리에서 +1
                    dis[nv] = dis[cv] +1;
                }
            }
        }
    }

    public static void main(String[] args) {
        BFS_dis bfs = new BFS_dis();

        Scanner scan = new Scanner(System.in);
        n = scan.nextInt(); // 도시의 갯수
        m = scan.nextInt(); // 도로의 갯수

        // 인접 리스트 생성 => Integer 를 담은 리스트를 담은 리스트
        graph = new ArrayList<ArrayList<Integer>>();

        for(int i=0; i<=n; i++){
            graph.add(new ArrayList<Integer>());
        }

        ch = new int[n+1];
        dis = new int[n+1];

        for(int i=0; i<m; i++){
            int a = scan.nextInt();
            int b = scan.nextInt();
            graph.get(a).add(b);
        }

        // 1 번 도시부터 시작
        bfs.dis(1);

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

결과 확인

• 녹색은 내가 넣은 도시의 번호와 연결된 도로이다.
• cv 는 현재 방문한 도시의 번호, nv 는 cv 와 연결되어 있으며, 다음 방문한 도시의 번호이다.
• 1번부터 시작한다고 했을 때 1번에서 3, 4 번 도시를 방문한다.
  • 3번 도시는 4번 도시외 연결된 도시가 없고, 4번 도시는 이미 1번 도시를 통해서 방문 했음으로 다음 방문할 도시가 없기 때문에 종료된다 ⇒ 거리 1
• 1번에서 4번 도시까지의 거리는 1이고, 4번 도시에서 방문할 수 있는 도시는 5, 6번이다. 이때 5, 6번까지으 거리는 4번까지의 거리 +1 이다 ⇒ dis[5] = dis[4] + 1, dis[6] = dis[4] + 1
  • 5번 도시 역시 3번과 마찬가지로 4번을 통해서 방문했고, 연결된 도시가 없음으로 종료된다 ⇒ 거리 2
  • 6번 도시까지의 거리도 2
• 2번 도시는 6번에서만 방문할 수 있고, 따라서 6번까지의 거리 +1 이 된다 ⇒ dis[2] = dis[6] +1
  • 거리는 3

•