📝 문제 설명

입력: 첫째 줄에 공백을 두고 정수 N, M, V를 한 줄에 입력 받는다.
- N: 정점의 개수
- M: 간선의 개수
- V: 탐색을 시작할 정점의 번호 (1 - N)
츨력: 첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다.
- V부터 방문된 점을 순서대로 출력
- 방문할 수 있는 정점이 여러개인 경우 정점 번호가 작은것을 먼저 방문
- 저 이상 방문할 수 있는 정점이 없는 경우 종료

💡 아이디어

첫 줄에서 정점 수 N, 간선 수 M, 시작 정점 V를 StringTokenizer로 한번에 파싱한다.
그래프는 인접 리스트 방식으로 표현한다.
- 각 정점마다 연결된 정점을 저장하기 위해 ArrayList<Integer>[] 배열을 사용
양방향 간선 입력을 위해 adj[a].add(b)와 adj[b].add(a)를 사용한다.
‘정점 번호가 작은 것 부터 방문한다’라는 규칙을 위해서 인접 리스트(adj[i])를 Collections.sort()로 오름차순으로 정렬한다.
DFS, BFS 탐색 출력에서, 방문 배열을 매번 초기화 해준다. (visited = new boolean[N + 1];) 그렇지 않으면 탐색 결과가 오염 될 수 있다.
DFS 로직은 재귀로 구현하고, BFS 로직은 큐로 구현한다.
- DFS는 v 방문 정점 자체를 매개변수로 받는다.
- BFS의 매개변수는 start로, 시작점만 정의해줄 뿐이다.
- 이후 인접 정점은 queue.offer()로 큐에 추가한다.
- 그러므로 .poll 함수를 사용해서 이미 방문한 정점은 삭제하여 정점 방문 순서를 제어한다.

🔎 예시 그래프 시각화

그래프

🛠 코드

✨ 제출 코드

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

public class Main {
    // 정점 수, 간선 수, 시작 정점 번호
    static int N, M, V;

    // 인접 리스트 (정점마다 연결된 정점 목록)
    static List<Integer>[] adj;

    // 방문 여부 저장 배열
    static boolean[] visited;

    public static void main(String[] args) throws IOException {
        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~N)
        adj = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) {
            adj[i] = 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());
            // 양방향 입력
            adj[a].add(b);
            adj[b].add(a);
        }
        
        // 작은 정점을 먼저 방문하기 위한 정렬
        for (int i = 1; i <= N; i++) {
            Collections.sort(adj[i]);
        }
        
        // DFS 출력
        visited = new boolean[N + 1];
        dfs(V);
        System.out.println();
        
        // BFS 출력
        visited = new boolean[N + 1];
        bfs(V);
        System.out.println();
    }
    
    // DFS - 재귀로 구현
    static void dfs(int v) {
        visited[v] = true;
        System.out.print(v + " ");
        for (int nxt : adj[v]) {
            if (!visited[nxt]) {
                dfs(nxt);
            }
        }
    }
    
    // BFS - 큐로 구현
    static void bfs(int start) {
        Queue<Integer> queue = new LinkedList<>();
        visited[start] = true;
        queue.offer(start);
        
        while (!queue.isEmpty()) {
            int v = queue.poll();
            System.out.print(v + " ");
            for (int nxt : adj[v]) {
                if (!visited[nxt]) {
                    visited[nxt] = true;
                    queue.offer(nxt);
                }
            }
        }
    }
}

🪄 디버깅 코드

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

public class Main {
    // 정점 수, 간선 수, 시작 정점 번호
    static int N, M, V;

    // 인접 리스트 (정점마다 연결된 정점 목록)
    static List<Integer>[] adj;

    // 방문 여부 저장 배열
    static boolean[] visited;

    public static void main(String[] args) throws IOException {
        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());
        System.out.println("N=" + N + ", M=" + M + ", V=" + V);

        // 그래프 초기화 (1~N)
        adj = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) {
            adj[i] = 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());

            adj[a].add(b); // a → b 연결
            adj[b].add(a); // b → a 연결
            System.out.println("간선 추가: " + a + " ↔ " + b);
        }

        // 작은 정점을 먼저 방문하기 위한 정렬
        for (int i = 1; i <= N; i++) {
            Collections.sort(adj[i]);
        }

        // 전체 그래프 구조 확인 출력
        System.out.println("정렬된 인접 리스트:");
        for (int i = 1; i <= N; i++) {
            System.out.println("  " + i + " → " + adj[i]);
        }
        System.out.println();

        // DFS 출력
        // DFS와 BFS는 서로 영향을 주지 않도록 visited 각각 초기화
        visited = new boolean[N + 1];
        System.out.println("===== DFS 시작 =====");
        dfs(V);
        System.out.println("\n===== DFS 종료 =====\n");

        // BFS 출력
        visited = new boolean[N + 1]; // 방문 배열 다시 초기화
        System.out.println("===== BFS 시작 =====");
        bfs(V);
        System.out.println("\n===== BFS 종료 =====");
    }

    // ===== DFS 함수 정의 =====
    // 깊이 우선 탐색: 가능한 한 깊게 들어가는 방식 (재귀로 구현)
    static void dfs(int v) {
        visited[v] = true; // 현재 정점 방문 처리
        System.out.println("[DFS] 방문 → " + v);

        // 현재 정점에 연결된 인접 정점들을 순서대로 확인
        for (int nxt : adj[v]) {
            System.out.println("  [DFS] " + v + "의 이웃 체크 → " + nxt);

            // 아직 방문하지 않았다면 재귀 호출로 계속 들어감
            if (!visited[nxt]) {
                System.out.println("    [DFS] → " + nxt + " 재귀 호출");
                dfs(nxt);
            } else {
                System.out.println("    [DFS] 이미 방문함 → " + nxt);
            }
        }
    }

    // ===== BFS 함수 정의 =====
    // 너비 우선 탐색: 가까운 노드부터 탐색하는 방식 (큐로 구현)
    static void bfs(int start) {
        Queue<Integer> queue = new LinkedList<>(); // 탐색에 사용할 큐
        visited[start] = true;                     // 시작 정점 방문 처리
        queue.offer(start);                        // 큐에 시작 정점 넣기
        System.out.println("[BFS] 시작 정점 → " + start);

        // 큐가 빌 때까지 반복
        while (!queue.isEmpty()) {
            // 큐에서 꺼내면서 현재 탐색할 정점 선택
            int v = queue.poll();
            System.out.println("[BFS] poll()로 큐에서 제거 → " + v);

            // 현재 정점과 연결된 모든 이웃 정점 확인
            for (int nxt : adj[v]) {
                System.out.println("  [BFS] " + v + "의 이웃 체크 → " + nxt);

                // 아직 방문하지 않은 정점이면 큐에 추가
                if (!visited[nxt]) {
                    visited[nxt] = true;
                    queue.offer(nxt);
                    System.out.println("    [BFS] 큐에 추가 → " + nxt);
                } else {
                    System.out.println("    [BFS] 이미 방문함 → " + nxt);
                }
            }
        }
    }
}

🪄 디버깅 코드 실행 결과

5 5 3
N=5, M=5, V=3
5 4
간선 추가: 5 ↔ 4
5 2
간선 추가: 5 ↔ 2
1 2
간선 추가: 1 ↔ 2
3 4
간선 추가: 3 ↔ 4
3 1
간선 추가: 3 ↔ 1
정렬된 인접 리스트:
  1 → [2, 3]
  2 → [1, 5]
  3 → [1, 4]
  4 → [3, 5]
  5 → [2, 4]

===== DFS 시작 =====
[DFS] 방문 → 3
  [DFS] 3의 이웃 체크 → 1
    [DFS] → 1 재귀 호출
[DFS] 방문 → 1
  [DFS] 1의 이웃 체크 → 2
    [DFS] → 2 재귀 호출
[DFS] 방문 → 2
  [DFS] 2의 이웃 체크 → 1
    [DFS] 이미 방문함 → 1
  [DFS] 2의 이웃 체크 → 5
    [DFS] → 5 재귀 호출
[DFS] 방문 → 5
  [DFS] 5의 이웃 체크 → 2
    [DFS] 이미 방문함 → 2
  [DFS] 5의 이웃 체크 → 4
    [DFS] → 4 재귀 호출
[DFS] 방문 → 4
  [DFS] 4의 이웃 체크 → 3
    [DFS] 이미 방문함 → 3
  [DFS] 4의 이웃 체크 → 5
    [DFS] 이미 방문함 → 5
  [DFS] 1의 이웃 체크 → 3
    [DFS] 이미 방문함 → 3
  [DFS] 3의 이웃 체크 → 4
    [DFS] 이미 방문함 → 4

===== DFS 종료 =====

===== BFS 시작 =====
[BFS] 시작 정점 → 3
[BFS] poll()로 큐에서 제거 → 3
  [BFS] 3의 이웃 체크 → 1
    [BFS] 큐에 추가 → 1
  [BFS] 3의 이웃 체크 → 4
    [BFS] 큐에 추가 → 4
[BFS] poll()로 큐에서 제거 → 1
  [BFS] 1의 이웃 체크 → 2
    [BFS] 큐에 추가 → 2
  [BFS] 1의 이웃 체크 → 3
    [BFS] 이미 방문함 → 3
[BFS] poll()로 큐에서 제거 → 4
  [BFS] 4의 이웃 체크 → 3
    [BFS] 이미 방문함 → 3
  [BFS] 4의 이웃 체크 → 5
    [BFS] 큐에 추가 → 5
[BFS] poll()로 큐에서 제거 → 2
  [BFS] 2의 이웃 체크 → 1
    [BFS] 이미 방문함 → 1
  [BFS] 2의 이웃 체크 → 5
    [BFS] 이미 방문함 → 5
[BFS] poll()로 큐에서 제거 → 5
  [BFS] 5의 이웃 체크 → 2
    [BFS] 이미 방문함 → 2
  [BFS] 5의 이웃 체크 → 4
    [BFS] 이미 방문함 → 4

===== BFS 종료 =====

⏱ 시간 복잡도

입력 처리:
M개의 간선을 읽고 인접 리스트(adj)에 추가 → O(M)
정렬:
각 정점에 대해 정렬 Collections.sort() 수행 → O(N * log D) (여기서 D는 각 정점의 평균 인접 정점 수, 최악의 경우 D = N) → 최악: O(N log N) (정점마다 연결된 정점이 많을 경우)
DFS (깊이 우선 탐색): 각 정점을 한번씩 방문하며 인접 정점 탐색 → O(N + M)
BFS (너비 우선 탐색): ‘큐를 이용해서’ 각 정점을 한번씩 방문하며 인접 정점 탐색 → O(N + M)
출력:
System.out.print()을 통한 순차 출력 → O(N) (최대 N개 정점 방문)

👉 총 시간 복잡도:
O(M + N log N)

✏️ 느낀 점

디버깅 코드로 처리과정을 모든 단계 톺아보는게 이해에 많은 도움이 됐다.
BFS는 최단 경로만 사용하므로 사용하지 않는 간선이 있다.