[1260] DFS와 BFS (JAVA)

# 문제 설명

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

---

입력

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

---

출력

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

 

# 정답 코드

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

public class Main {
    static ArrayList<Integer>[] A;
    static boolean[] visited;
    static StringBuilder sb;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        sb = new StringBuilder();

        int N = Integer.parseInt(st.nextToken()); //정점의 개수
        int M = Integer.parseInt(st.nextToken()); //간선의 개수
        int V = Integer.parseInt(st.nextToken()); //탐색을 시작할 정점의 번호

        A = new ArrayList[N+1];
        for (int n = 1; n <= N; n++) {
            A[n] = new ArrayList<>();
        }

        for (int m = 0; m < M; m++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());

            A[s].add(e);
            A[e].add(s);
        }

        for (int i = 1; i <= N; i++) {
            Collections.sort(A[i]);
        }

        visited = new boolean[N+1];
        dfs(V);

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

        System.out.print(sb);
    }

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

        for (int i : A[v]) {
            if (!visited[i]) {
                dfs(i);
            }
        }
    }

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

        while (!queue.isEmpty()) {
            int now = queue.poll();
            sb.append(now + " ");

            for (int i : A[now]) {
                if (!visited[i]) {
                    visited[i] = true;
                    queue.add(i);
                }
            }
        }
    }
}

 

bfs와 dfs를 사용하여 결과를 출력하는 문제이다.

인접 리스트에 그래프를 저장한다.

방문할 수 있는 노드가 여러 개일 때, 번호가 작은 것을 먼저 방문하기 위해 오름차순 정렬해준다.

 

방문 체크 배열 visited를 초기화하고 dfs를 V번 노드를 시작 노드로 하여 실행한다.

dfs 함수는 현재 노드 v를 출력하고 visited[v]를 true로 바꾼다.

v의 방문하지 않은 인접 노드들을 재귀 함수를 통해 탐색한다.

 

dfs가 끝나고 방문 체크 배열을 다시 초기화한다.

마찬가지로 V번 노드를 시작 노드로 하여 bfs를 실행한다.

큐에 현재 노드 v를 넣고 visited[v]를 true로 바꾼다.

 

큐가 빌 때까지 반복하며 bfs를 실행한다.

큐에서 꺼낸 노드를 now에 저장하고 now를 출력한다.

now의 방문하지 않은 인접 노드들을 큐에 넣고 방문 체크 배열을 true로 바꾼다.