[BFS] 그래프 최단거리 (인접리스트: ArrayList)

설명

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

 

 

첫번째 줄에 정점의 수n(1<=n<=20)과 간선의 수m이 주어진다.

두번째 줄부터는 연결정보가 주어진다.

 

입력

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

 

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static ArrayList<ArrayList<Integer>> gr;
    static int n;
    static int[] count;
    static int[] ch;

    public static void BFS(int k){
        Queue<Integer> q = new LinkedList<>();
        q.offer(k);
        int L=0;

        while(!q.isEmpty()){
            int len = q.size();
            for(int i=0;i<len;i++){
                int curr = q.poll();
                ch[curr] =1;
                count[curr] = Math.min(L, count[curr]);
                for(int e : gr.get(curr)){
                    if(ch[e]!=1) q.offer(e);
                }
            }
            L++;
        }

    }

    public static void  main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader( System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        gr = new ArrayList<ArrayList<Integer>>();
        count = new int[n+1];
        ch = new int[n+1];

        for(int i=0;i<=n;i++){
            gr.add(new ArrayList<Integer>());
            count[i] = Integer.MAX_VALUE;
        }

        for(int i=0;i<m;i++){
            StringTokenizer st2 = new StringTokenizer(br.readLine(), " ");
            int r = Integer.parseInt(st2.nextToken());
            int c = Integer.parseInt(st2.nextToken());
            gr.get(r).add(c);
        }

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


    }
}

 

주어진 그래프를 트리 형태로 그리면 위와 같은 형태가 된다.

이 상태에서 중복되는 숫자를 제거하고 BFS로 레벨 탐색을 통해 최단 거리를 구하면 된다.

-> 중복제거를 안하면 계속 서로를 가르키며 안끝날수가 있음.

 

 

++) 더 나은 방법

public static void BFS(int k){
    Queue<Integer> q = new LinkedList<>();
    q.offer(k);

    while(!q.isEmpty()){
       int curr = q.poll();
       for(int e : gr.get(curr)){
           if(ch[e]==0){
               ch[e] =1;
               q.offer(e);
               count[e] = count[curr]+1;
            }
        }
    }
}