[백준 1260] Java - dfs, bfs / 가능한 작은 정점 방문하는 경우

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

// The main method must be in a class named "Main".
class Main {
    static int N, M, V; //정점, 간선 개수, 시작할 정점 번호
    static ArrayList<Integer>[] adjList; // 인근 정점
    static boolean[] visited; //정점 방문 여부
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        // 정점 개수, 간선 개수, 시작할 정점 번호 입력받기
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        V = Integer.parseInt(st.nextToken());

        // 정점 번호 1번부터
        adjList = new ArrayList[N+1];
        for(int i=1; i<=N;i++){
            adjList[i] = new ArrayList<>();
        }
        visited = new boolean[N+1];
        
        //간선이 연결하는 두 정점 입력받기
        for(int i=1; i<=M;i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            // 방향X
            adjList[a].add(b);
            adjList[b].add(a);
        }

        //문제 조건 : 정점 번호가 작은 것 먼저 방문 > 정점 정렬하기
        for(int i = 1; i <= N; i++) {
            Collections.sort(adjList[i]);
        }

        
        //dfs 수행 결과 출력
        dfs(V);
        System.out.println();
        
        //bfs 수행 결과 출력
        Arrays.fill(visited, false);
        bfs(V);

        br.close();
    } //main

    //dfs
    static void dfs(int start){
        visited[start] = true;
        System.out.print(start+" ");
        
        for(int n: adjList[start]){
            if(visited[n]){
                continue;
            }
            visited[n] = true;  
            dfs(n);
        }
    }

    //bfs
    static void bfs(int start){
        System.out.print(start+" ");
        ArrayDeque<Integer> q = new ArrayDeque<>();
        q.offer(start);
        visited[start] = true;

        while(!q.isEmpty()){
            int current = q.poll();
            for(int n: adjList[current]){
                if(visited[n]){
                    continue;
                }
                System.out.print(n+" ");
                visited[n] = true;
                q.offer(n);
            }
        }
    }
}

 

🔵 방문할 수 있는 정점이 여러 개인 경우 > 정점 번호가 작은 것 먼저 방문하는 경우

인접 리스트를 정렬 → 각 정점의 이웃들을 번호 순서대로 방문할 수 있도록 준비

BFS에서 일반 큐 사용 → BFS의 핵심인 레벨 순서를 유지하면서, 정점 번호가 작은 순서대로 탐색.

for (int i = 1; i <= N; i++) {
    Collections.sort(adjList[i]); // 작은 정점 우선 방문을 위해 정렬
}

 

🔵정점 번호 순서가 상관없는 경우

인접 리스트를 정렬할 필요 없이 그냥 BFS를 수행