백준 24444번 : 알고리즘 수업 - 너비 우선 탐색 1 java

이 문제는 bfs를 이용하여 정점들을 탐색하면서 각 정점별로 호출된 순서를 출력하는 문제입니다.

이 문제의 예제를 통해 설명드리도록 하겠습니다.

이 문제의 예제를 그래프로 나타내면 다음과 같습니다.

시작 정점이 1번이니 여기서 시작하여 bfs를 순서대로 실행하는 모습을 보여드리겠습니다.

bfs를 통해서 순서를 타고 내려갈 때 정점의 수가 적은 순으로 내려가니 그다음은 2번 노드와 4번 노드 중에서 2번 노드로 갑니다.

이제 2번 노드를 탐색했으니 1번 노드와 연결되어 있던 4번 노드를 탐색해줍니다.

이제 2번 노드와 연결되어 있던 3번 정점을 탐색해줍니다.

5번 정점을 갈 수 없으므로 0을 넣어줍니다.

다음과 같은 알고리즘으로 이 문제를 해결하실 수 있습니다.

---

import java.io.*;
import java.util.*;

public class Main {
    static int N, M;
    static List<List<Integer>> l = new ArrayList<>();
    static int[] visited;

    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());
        M = Integer.parseInt(st.nextToken());
        int R = Integer.parseInt(st.nextToken());

        visited = new int[N+1];
        for(int i = 0; i<=N; i++)
            l.add(new ArrayList<>());

        for(int i = 0; i<M; i++){
            st = new StringTokenizer(br.readLine());

            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());

            l.get(A).add(B);
            l.get(B).add(A);
        }

        for(int i = 1; i<=N; i++)
            Collections.sort(l.get(i));

        bfs(R);

        for(int i = 1; i<=N; i++)
            System.out.println(visited[i]);
    }

    static void bfs(int start){
        Queue<Integer> q = new LinkedList<>();
        int cnt = 1;

        q.offer(start);
        visited[start] = cnt++;

        while(!q.isEmpty()){
            int a = q.poll();

            for(int i = 0; i<l.get(a).size(); i++){
                int nextV = l.get(a).get(i);

                if(visited[nextV] != 0)
                    continue;

                q.offer(nextV);
                visited[nextV] = cnt++;
            }
        }
    }
}