백준 1260번: DFS와 BFS

풀이 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;


public class Main {

    static int[][] arr;
    static boolean[] visited;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int V = Integer.parseInt(st.nextToken());


        arr = new int[N+1][N+1];
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());

            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            arr[a][b] = 1;
            arr[b][a] = 1;
        }

        visited = new boolean[N+1];

        dfs(V);

        System.out.println();

        visited = new boolean[N + 1];

        bfs(V);

        System.out.println();

        
    }

    public static void dfs(int v) {
        visited[v] = true;
        System.out.print(v + " ");

        if (v == arr.length) return;

        for (int i = 1; i < arr.length; i++) {
            if (arr[v][i] == 1 && visited[i] == false) {
                dfs(i);
            }
        }

    }

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

        System.out.print(v + " ");

        while(!queue.isEmpty()) {
            int n = queue.poll();

            for (int i = 1; i < arr.length; i++) {
                if (arr[n][i] == 1 && visited[i] == false) {
                    visited[i] = true;
                    System.out.print(i + " ");
                    queue.offer(i);
                }
            }
        }

    }



}

1. 그래프 입력 및 정렬

• ArrayList<Integer>[] graph를 사용하여 인접 리스트 방식으로 그래프를 저장.
• 간선 정보 입력 후, Collections.sort(graph[i])로 정점 번호가 작은 것부터 방문하도록 정렬.

2. DFS (깊이 우선 탐색)

• 재귀 방식 사용.
• 방문한 노드를 출력하고, 방문하지 않은 연결된 정점들을 재귀 호출.
• visited 배열을 사용하여 방문 여부 체크.

3. BFS (너비 우선 탐색)

• Queue<Integer>를 사용하여 구현.
• queue.poll()로 현재 노드를 꺼내고 방문한 후, 인접한 정점 중 방문하지 않은 정점을 큐에 추가.
• 방문한 정점을 visited 배열로 체크.

---

시간 복잡도 분석

• DFS: O(N + M) (정점 + 간선 개수)
• BFS: O(N + M) (정점 + 간선 개수)
• 인접 리스트 사용 시 평균적으로 O(N + M) 시간 복잡도를 가짐.