문제 출처

단계별로 풀어보기 > 그래프와 순회 > DFS와 BFS
https://www.acmicpc.net/problem/1260

문제 설명

DFS와 BFS를 구현하라.
정점의 개수 N, 간선의 개수 M, 시작 정점의 개수 V가 주어질 때, 각각 DFS, BFS의 결과를 출력하라.

접근 방법

인접 리스트 형식으로 DFS, BFS를 구현한다.

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

public class DFS와_BFS {
    public static List<List<Integer>> graph = new ArrayList<>();
    public static boolean visitedDFS[];
    public static boolean visitedBFS[];
    public static StringBuilder sb = new StringBuilder();

    public static void dfs(int start){
        visitedDFS[start] = true;
        sb.append(start).append(" ");
       for(int next : graph.get(start)){
           if(!visitedDFS[next]) dfs(next);
       }
    }

    public static void bfs(int start){
        Queue<Integer> q = new LinkedList<>();
        visitedBFS[start] = true;
        q.add(start);

        while(!q.isEmpty()){
            int cur = q.poll();
            sb.append(cur).append(" ");
            for(int next : graph.get(cur)){
                if(!visitedBFS[next]){
                    visitedBFS[next] = true;
                    q.offer(next);
                }
            }
        }
    }

    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());

        visitedDFS = new boolean[N+1];
        visitedBFS = new boolean[N+1];

        for(int i = 0; i <= N; i++) graph.add(new ArrayList<>());

        for(int i = 0; i < M; i++){
            st = new StringTokenizer(br.readLine());
            int k = Integer.parseInt(st.nextToken());
            int l = Integer.parseInt(st.nextToken());

            graph.get(k).add(l);
            graph.get(l).add(k);
        }

        for(int i = 1; i <= N; i++) Collections.sort(graph.get(i));

        dfs(V);
        sb.append("\n");
        bfs(V);

        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();
    }
}

알게된 점

지금까지는 인접 행렬로만 구현해보았고, 인접 리스트는 처음 써봐서 생각보다 해맸다.

시간 복잡도는 인접리스트 방식이므로 O(V + E)이다. 추가로 정렬이 들어가므로, O(V + E log V)가 된다.

문제푼 흔적