백준 24444 문제 [BFS]

입력

첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다.
다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양방향 간선을 나타낸다. (1 ≤ u < v ≤ N, u ≠ v) 모든 간선의 (u, v) 쌍의 값은 서로 다르다.

출력

첫째 줄부터 N개의 줄에 정수를 한 개씩 출력한다. i번째 줄에는 정점 i의 방문 순서를 출력한다. 시작 정점의 방문 순서는 1이다. 시작 정점에서 방문할 수 없는 경우 0을 출력한다.

서론

처음으로 넓이 우선 탐색 문제를 마주하였다. 해결 방안이 아예 떠오르지않아 동빈나님의 강의를 보고 문제를 이해하였다!!👍👍

풀이

처음에는 그래프를 그려 이해를 하고자하였다. 그리고 강의에서 굉장히 인상 깊었던 부분이 있었다.

ArrayList<ArrayList<Integer>>

바로 이부분이다! ArrayList안에 ArrayList를 구현하여 이차원 리스트 느낌을 구현하신것 같았다.
이를 구현하면
[1,3],[1,4],[2,3],[3,5]
처럼 리스트 내부를 형성할 수 있었다. 또한 Queue를 사용하여 넓이 우선 탐색을 구현하였다.😙

코드 구현

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

public class B_24444 {

    static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
    static boolean[] visited;
    static int[] result;
    static int order = 1;
    static Queue<Integer> queue = new LinkedList<>();
    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 boolean[N + 1];
        result = new int[N + 1];
        for (int i = 0; i <= N; i++) {
            graph.add(new ArrayList<>());
        }

        for (int i = 1; i <= M; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());

            graph.get(u).add(v);
            graph.get(v).add(u);
        }
        
        //graph 내부 오름차순 정렬 
        //예 : [4,1],[3,1] -> [1,4],[1,3]
        for (int i = 1; i <= N; i++) {
            Collections.sort(graph.get(i));
        }
        
        bfs(R);
        
        //결과출력
        for (int i = 1; i <= N; i++) {
            bw.write(result[i] + "\n");
        }

        bw.flush();
        bw.close();
        br.close();
    }

    //bfs 구현
    public static void bfs(int node) {
        queue.offer(node);
        visited[node] = true;

        while (!queue.isEmpty()) {
            int x = queue.poll();
            result[x] = order++;
            for (int i = 0; i < graph.get(x).size(); i++) {
                int y = graph.get(x).get(i);
                if (!visited[y]) {
                    queue.offer(y);
                    visited[y] = true;
                }
            }
        }
    }
}