[자바] 백준 24444번 알고리즘 수업 - 너비 우선 탐색 1

https://www.acmicpc.net/problem/24444

 

값 입력 받는 건 동일하지만 bfs 함수 구현하는 것만 차이가 있다. 

queue를 하나 만들고 시작 정점부터 정점에 인접한 정점 중 작은 수부터 방문하게 된다. 이때 dfs는 예를 들어 정점 1과 인접한 정점이 2, 4가 있었을 때 2를 방문한 뒤에는 2와 인접한 정점을 방문하게 되는데 bfs의 경우는 2를 방문한 뒤, 1과 인접해있는 4를 그 다음으로 방문하게 된다는 게 차이가 있다. 즉, graph.get(1) 의 모든 결과 값을 다 방문하도록 구현해야돼서 큐를 사용한다고 생각하면 된다.

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

public class Main {

    public static int[] visited;
    public static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();

    // 순서 저장을 위한 변수
    public static int count = 0;

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

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int r = Integer.parseInt(st.nextToken());

        visited = new int[n+1];

        // 그래프 초기화
        for(int i = 0; i <= n; i++){
            graph.add(new ArrayList<Integer>());
        }

        // 그래프에 값 넣기
        for(int i = 0; i < m; i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            graph.get(a).add(b);
            graph.get(b).add(a);
        }

        for(int i = 1; i <= n; i++){
            Collections.sort(graph.get(i));
        }

        // bfs
        count++;
        bfs(r);

        for(int i = 1; i < visited.length; i++){
            bw.write(String.valueOf(visited[i] + "\n" ));
        }
        bw.flush();
        bw.close();
    }
    public static void bfs(int r){
        Queue<Integer> q = new LinkedList<>(); // queue를 linkedlist로 구현

        q.add(r);
        visited[r] = count;

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

            for(int i = 0; i < graph.get(a).size(); i++){
                int v = graph.get(a).get(i);
                if(visited[v] != 0) continue;
                q.offer(v);
                count++;
                visited[v] = count;
            }
        }
    }
}