BFS, 인접리스트

✅ 1번 정점에서 각 정점으로 가는 최소 이동 간선 수를 구하세요

🔑 BFS 키워드

최소 이동 간선 수
BFS는 QUEUE를 사용한다

✔️ graph

✔️ input

6 9
1 3
1 4
2 1
2 5
3 4
4 5
4 6
6 2
6 5

✔️ output

2: 3
3: 1
4: 1
5: 2
6: 2

🟢 레벨 없이 풀기

class Main {
    static int n;
    static int m;

    static ArrayList<ArrayList<Integer>> graph;

    static int[] ch;
    static int[] dis;


    public void BFS(int v) {
        Queue<Integer> Q= new LinkedList<>();
        Q.offer(v);
        ch[v]=1;
        dis[v]=0;
        while(!Q.isEmpty()){
            int cur= Q.poll();
            ArrayList<Integer> curList= graph.get(cur);
            for(int x: curList){
                if(ch[x]==0){
                    Q.offer(x);
                    ch[x]=1;
                    dis[x]= 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<>());
        }
        for (int j = 0; j < m; j++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            graph.get(a).add(b);
        }
        T.BFS(1);
        for(int k=2; k<=n; k++){
            System.out.println(k + ":"+ dis[k]);
        }
    }
}

🟢 레벨로 풀기

class Main {
    static int n;
    static int m;

    static ArrayList<ArrayList<Integer>> graph;  //인접 리스트

    static int[] ch; //체크배열
    static int[] dis; //거리 저장할 배열, 예를 들어 dis[3]은 1번 노드부터 3번 노드까지 간선 수

    public void BFS(int v) {
        Queue<Integer> Q= new LinkedList<>(); //BFS는 QUEUE
        Q.offer(v);
        ch[v]=1;
        dis[v]=0;
        int L=0;
        while(!Q.isEmpty()){
            int len= Q.size(); //len이 계속 변하기 때문에 변수 설정 필요
            for(int i=0; i<len; i++){
                int cur= Q.poll();
                dis[cur] = L;
                ArrayList<Integer> curList= graph.get(cur); //인접 리스트에서 지금 있는 노드와 연결된 노드들 가져오기
                for(int x: curList){
                    if(ch[x] ==0 ){ //방문 안했으면
                        ch[x]=1;
                        Q.offer(x);
                    }
                }
            }
            L++;
        }
    }

    public static void main(String[] args) {
        Main T = new Main();n
        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<>());
        }
        for (int j = 0; j < m; j++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            graph.get(a).add(b);
        }
        T.BFS(1);
        for(int k=2; k<=n; k++){
            System.out.println(k + ":"+ dis[k]);
        }
    }
}