DFS, BFS

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

public class Main {

    static boolean[] visited;
    static ArrayList<Integer>[] adjList;
    static StringBuilder dfsResult = new StringBuilder();
    static StringBuilder bfsResult = new StringBuilder();

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

        adjList = new ArrayList[N + 1]; 
        for (int i = 1; i <= N; i++) {
            adjList[i] = new ArrayList<>();
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            adjList[u].add(v);
            adjList[v].add(u);
        }

        for (int i = 1; i <= N; i++) {
            Collections.sort(adjList[i]);
        }

        visited = new boolean[N + 1];
        dfs(V);
        bw.write(dfsResult.toString() + "\n");

        visited = new boolean[N + 1];
        bfs(V);
        bw.write(bfsResult.toString() + "\n");

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

    static void dfs(int v) {
        visited[v] = true;
        dfsResult.append(v).append(" ");

        for (int next : adjList[v]) {
            if (!visited[next]) {
                dfs(next);
            }
        }
    }

    static void bfs(int start) {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(start);
        visited[start] = true;

        while (!queue.isEmpty()) {
            int v = queue.poll();
            bfsResult.append(v).append(" ");

            for (int next : adjList[v]) {
                if (!visited[next]) {
                    visited[next] = true;
                    queue.offer(next);
                }
            }
        }
    }
}

📌 1. BufferedReader와 BufferedWriter

1) BufferedReader

• BufferedReader는 Java에서 입력을 빠르게 읽어오는 클래스입니다.
• System.in을 직접 사용하는 Scanner보다 속도가 빠릅니다.
• 입력을 한 줄씩 읽을 수 있기 때문에, readLine() 메서드를 사용합니다.
• 한 줄의 입력을 띄어쓰기로 구분된 여러 개의 값으로 나누기 위해 StringTokenizer를 활용합니다.

2) BufferedWriter

• BufferedWriter는 출력 속도를 향상시키는 클래스입니다.
• System.out.println()보다 성능이 우수합니다.
• write() 메서드를 사용하여 출력 데이터를 버퍼에 저장하고, flush()로 한 번에 출력합니다.

---

📌 2. DFS (Depth-First Search, 깊이 우선 탐색)

• 그래프 탐색 기법 중 하나로, 한 방향으로 끝까지 탐색한 후 다시 돌아와 다른 경로를 탐색하는 방식입니다.
• 스택(Stack) 또는 재귀(Recursion)를 활용하여 구현할 수 있습니다.

✅ DFS 동작 원리

1. 시작 노드를 방문하고 출력한다.
2. 현재 노드와 연결된 아직 방문하지 않은 노드로 이동한다.
3. 더 이상 이동할 곳이 없으면 되돌아가며 다른 경로를 탐색한다.
4. 모든 노드를 방문할 때까지 반복한다.

---

📌 3. BFS (Breadth-First Search, 너비 우선 탐색)

• 그래프 탐색 기법 중 하나로, 시작 노드에서 가까운 노드부터 차례대로 탐색하는 방식입니다.
• 큐(Queue)를 활용하여 구현합니다.

✅ BFS 동작 원리

1. 시작 노드를 방문하고 큐(Queue)에 삽입한다.
2. 큐에서 노드를 꺼낸 후, 해당 노드와 연결된 방문하지 않은 노드를 큐에 추가한다.
3. 큐가 빌 때까지 반복한다.

---

2️⃣ 코드 상세 분석

• visited[] → 각 노드의 방문 여부를 저장하는 배열입니다.
• adjList[] → 각 노드에 연결된 다른 노드들의 정보를 저장하는 인접 리스트입니다.
• 빠른 입출력을 위한 BufferedReader와 BufferedWriter 사용합니다.
• StringTokenizer를 이용해 띄어쓰기 기준으로 입력 값을 분리합니다.
• 인접 리스트(ArrayList)를 생성하여 각 노드에 연결된 노드를 저장할 공간을 만듭니다.

 

• 입력된 간선을 인접 리스트에 저장합니다.
• adjList[u].add(v) → u 노드에서 v 노드로 연결
• adjList[v].add(u) → v 노드에서 u 노드로 연결
  (양방향 그래프이므로 서로 연결)

 

for (int i = 1; i <= N; i++) { Collections.sort(adjList[i]); }

• DFS와 BFS가 작은 숫자부터 방문하도록 리스트를 정렬합니다.

 

visited = new boolean[N + 1]; dfs(V); bw.write(dfsResult.toString() + "\n");

• dfs(V)를 호출하여 DFS 탐색을 수행합니다.
• 결과를 StringBuilder에 저장하고, 마지막에 한 번에 출력합니다.

 

visited = new boolean[N + 1]; bfs(V); bw.write(bfsResult.toString() + "\n");

• bfs(V)를 호출하여 BFS 탐색을 수행합니다.

 

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

• 버퍼에 남아 있는 데이터를 한 번에 출력하고 종료합니다.