[백준1260/자바] DFS와 BFS

문제

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

입력

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

출력

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

 

---

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class BJ1260 {

    static List<LinkedList<Integer>> graph;
    static boolean[] visited;
    static int visitedCnt;
    static StringBuilder result;

    public static void main(String[] args) throws IOException {
        // N, M, V 입력
        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());

        // 그래프 생성 및 초기화 (LinkedList)
        graph = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
            graph.add(new LinkedList<>());
        }

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

            graph.get(num1).add(num2);
            graph.get(num2).add(num1);
        }

        for (int i = 1; i <= N; i++) {     // 작은 값 먼저 가져올 수 있게 오름차순 정렬
            graph.get(i).sort((o1, o2) -> o1 - o2);
        }

        // dfs
        result = new StringBuilder();
        result.append(V + " ");

        visited = new boolean[N + 1];
        Arrays.fill(visited, false);
        visited[V] = true;
        visitedCnt = 1;

        dfs(V, N);
        System.out.println(result);

        // bfs
        result = new StringBuilder();
        result.append(V + " ");

        visited = new boolean[N + 1];
        Arrays.fill(visited, false);
        visited[V] = true;
        visitedCnt = 1;

        bfs(V, N);
        System.out.println(result);
    }

    static void dfs(int curPoint, int N) {
        if (visitedCnt == N) {
            return;
        }

        for (int i = 0; i < graph.get(curPoint).size(); i++) {
            int point = graph.get(curPoint).get(i);
            if (!visited[point]) {
                visited[point] = true;
                visitedCnt++;
                result.append(point + " ");
                dfs(point, N);
            }
        }
    }

    static void bfs(int start, int N) {
        Queue<Integer> queue = new LinkedList<>();
        queue.addAll(graph.get(start));
        while(visitedCnt < N && !queue.isEmpty()) {
            int point = queue.poll();
            if (!visited[point]) {
                visited[point] = true;
                visitedCnt++;
                result.append(point + " ");
                queue.addAll(graph.get(point));
            }

        }
    }
}