BFS level 구하기

참고: https://kks227.blog.me/220785747864

package com.company;

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

public class Main {

    static int N, E, startPoint;
    static int[][] graph;
    static int pos;
    static boolean[] visitied;

    static Scanner sc = new Scanner(System.in);

    public static void main(String[] args) {
       // write your code here
        N = sc.nextInt();
        E = sc.nextInt();
        startPoint = sc.nextInt();

        graph = new int[1001][1001];
        visitied = new boolean[N+1];


        //인접행렬을 완성
        int v1, v2;
        for(int i=1; i<=E; i++){
            v1 = sc.nextInt();
            v2 = sc.nextInt();

            graph[v1][v2] = 1;
            graph[v2][v1] = 1;
        }
        bfs(startPoint);
    }

    static void bfs(int startPoint){

        Queue<Integer> queue = new LinkedList<>();

        //시작지점 처리
        visitied[startPoint] = true;
        queue.offer(startPoint);

        int level = 0; //시작지점으로부터의 거리


        while ( !queue.isEmpty() ){ //큐가 빌때까지 돈다

            System.out.println("========== level: " + level + " ==========");

            int qSize = queue.size();
            for(int i=1; i<=qSize; i++){
                pos = queue.poll();
                System.out.println(pos + " ");

                //인접영역 탐색
                for(int j=1; j<=E; j++){
                    if( graph[pos][j]==1 && visitied[j]==false ){ //연결되어 있고 밤문하지 않은 경우
                        queue.offer(j);
                        visitied[j] = true;
                    }
                }//for(j)
            }//for(i)

            level++;

        }//while

    }
}

[input]

5 6 2

1 2

1 3

2 4

3 4

3 5

4 5

[output]

========== level: 0 ==========

2 

========== level: 1 ==========

1 

4 

========== level: 2 ==========

3 

5 

잘못된 코드

for(i)문 안에서 반복의 끝인 queue.size()의 크기가 변화된다.

반복의 크기는 고정되어야 함

    while ( !queue.isEmpty() ){ //큐가 빌때까지 돈다

        System.out.println("========== level: " + level + " ==========");
         
        for(int i=0; i<queue.size(); i++){
            pos = queue.poll();
            System.out.println(pos + " ");

            //인접영역 탐색
            for(int j=1; j<=E; j++){
                if( graph[pos][j]==1 && visitied[j]==false ){ //연결되어 있고 밤문하지 않은 경우
                    queue.offer(j);
                    visitied[j] = true;
                }
            }//for(j)
        }//for(i)
        
        level++;

    }//while

위처럼 요렇게..

int qSize = queue.size();

for(int i=1; i<=qSize; i++){ ...