(1260번) DFS와 BFS

문제

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

입력

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

출력

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

---

문제 풀이

해당 문제는 그래프탐색 BFS와 DFS를 통해서 풀 수 있는 문제이다.

 

DFS(Depth First Search)란 깊이 우선 탐색으로 해당 노드에 연결된 다음 노드를 탐색 -> 다음 노드에 연결된 그 다음의 노드를 탐색하면서 한번 끝까지 갔다가 돌아오는 탐색 방식이다. 

 

BFS(Breadth First Searth)란 너비 우선 탐색으로 기준이 되는 노드에서 깊이가 제일 가까운 노드들 부터 먼저 탐색 하는 방식이다. 

 

우선 해당 문제에서는 그래프가 양방향이므로 인접리스트를 통해 노드간의 연결 구조를 만들어 준다. 

만들어진 인접리스트를 통해 그래프를 만들어 보면 아래와 같은 모양이 나온다. 

이 이후에 1번을 기준으로 DFS를 수행하고 BFS를 순회하면 되는데, 우선 문제에서 작은 번호를 순차대로 확인하라고 하였으므로 위에 만들어진 리스트를 정렬을 수행하고 진행해야한다. 

 

DFS는 스택을 사용하면 구현되는 문제이고, BFS는 큐를 이용하면 구현할 수 있다.

---

나의 답안

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

public class Main {

    static List<Integer> graph[];
    static boolean[] visited;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int e = sc.nextInt();
        int s = sc.nextInt();

        graph = new ArrayList[n + 1];

        for (int i = 0; i < n + 1; i++) {
            graph[i] = new ArrayList<>();
        }

        for (int i = 0; i < e; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();

            graph[u].add(v);
            graph[v].add(u);
        }

        for (int i = 0; i < n + 1; i++) {
            Collections.sort(graph[i]);
        }

        visited = new boolean[n + 1];
        dfs(s);
        sb.append("\n");

        visited = new boolean[n + 1];
        bfs(s);
        sb.append("\n");

        System.out.println(sb.toString());

    }

    private static void bfs(int node) {
        Queue<Integer> queue = new LinkedList<>();

        visited[node] = true;
        queue.add(node);
        sb.append(node + " ");

        while (!queue.isEmpty()) {
            int cur = queue.poll();
            for (int next : graph[cur]) {
                if (!visited[next]){
                    visited[next] = true;
                    sb.append(next + " ");
                    queue.add(next);
                }
            }
        }

    }

    private static void dfs(int node) {
        visited[node] = true;
        sb.append(node + " ");

        for (int next : graph[node]) {
            if (!visited[next]) {

                dfs(next);
            }
        }
    }
}