[BOJ] 백준 1206번 DFS와 BFS - 인접 리스트 JAVA 풀이

import java.io.*;
import java.util.*;
import java.util.stream.Collectors;

class Main {
    static Map<Integer, LinkedList<Integer>> graph = new HashMap<>();
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws Exception {
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken()); // 정점 수
        int M = Integer.parseInt(st.nextToken()); // 간선 수
        int V = Integer.parseInt(st.nextToken()); // 탐색 시작점

        initGraph(M); // 1. 인접리스트 그래프 초기화
        List<Integer> discoveredDfs = dfs(V, new ArrayList<>()); // 2. DFS
        List<Integer> discoveredBfs = bfs(V); // 3. BFS

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String dfs = discoveredDfs.stream().map(String::valueOf).collect(Collectors.joining(" "));
        String bfs = discoveredBfs.stream().map(String::valueOf).collect(Collectors.joining(" "));

        bw.write(dfs + "\n" + bfs);
        bw.flush();
        bw.close();
    }

    public static void initGraph(int M) throws IOException {
        while(M-- > 0) {
            StringTokenizer edge = new StringTokenizer(br.readLine());
            int v = Integer.parseInt(edge.nextToken());
            int w = Integer.parseInt(edge.nextToken());

            addVertex(v, w);
            addVertex(w, v);
        }
        graph.forEach((key, list) -> Collections.sort(list));
    }

    public static void addVertex(int p, int q) {
        if(graph.containsKey(p))
            graph.get(p).add(q);
        else {
            LinkedList<Integer> list = new LinkedList<>();
            list.add(q);
            graph.put(p, list);
        }
    }

    public static List<Integer> dfs(int v, List<Integer> discovered) {
        discovered.add(v);

        if(!graph.containsKey(v)) // v에 인접한 정점이 없을 때 리턴
            return discovered;

        for(int w : graph.get(v)) // v의 인접 정점들 중 미방문 정점에 대해 dfs 수행
            if(!discovered.contains(w))
                dfs(w, discovered);

        return discovered;
    }

    public static List<Integer> bfs(int st_v) {
        List<Integer> discovered = new ArrayList<>();
        Queue<Integer> queue = new LinkedList<>();

        discovered.add(st_v);
        queue.add(st_v);

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

            if(!graph.containsKey(v)) // v에 인접한 정점이 없을 때 패스
                continue;

            for(int w : graph.get(v)) // v의 인접 정점들 중 미방문 정점들에 대해 큐에 삽입
                if(!discovered.contains(w)) {
                    discovered.add(w);
                    queue.add(w);
                }
        }
        return discovered;
    }
}