DFS와 BFS

[yu-heejin]

https://www.acmicpc.net/problem/1260

[yu-heejin]

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

public class Main {

  public static void main(String args[]) throws Exception {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

      String[] input = br.readLine().split(" ");

      int N = Integer.parseInt(input[0]);
      int M = Integer.parseInt(input[1]);
      int V = Integer.parseInt(input[2]);

      List<List<Integer>> graph = new ArrayList<>();

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

      for (int i = 0; i < M; i++) {
          input = br.readLine().split(" ");

          int a = Integer.parseInt(input[0]);
          int b = Integer.parseInt(input[1]);

          graph.get(a).add(b);
          graph.get(b).add(a);
      }

      dfs(graph, V);
      bfs(graph, V);
  }

  private static void dfs(List<List<Integer>> graph, int V) {
      // 깊이 우선 탐색
      boolean[] visited = new boolean[graph.size()];
      Stack<Integer> s = new Stack<>();

      visited[V] = true;
      // stack을 사용하기 때문에 먼저 들어간 요소가 나중에 나온다.
      s.push(V);

      while (!s.isEmpty()) {
          int curr = s.pop();
          List<Integer> connection = graph.get(curr);

          System.out.print(curr + " ");

          // 가장 작은 수부터 방문
          //Collections.sort(connection, Collections.reverseOrder());
          // 해당 지점과 연결된 다른 정점
          for (int c : connection) {
            if (!visited[c]) {
              visited[c] = true;
              s.push(c);
            }
          }
      }

      System.out.println();
  }

  private static void bfs(List<List<Integer>> graph, int V) {
      boolean[] visited = new boolean[graph.size()];
      Queue<Integer> q = new LinkedList<>();

      visited[V] = true;
      q.add(V);

      while (!q.isEmpty()) {
          int curr = q.poll();
          List<Integer> connection = graph.get(curr);

          System.out.print(curr + " ");

          // 가장 작은 수부터 방문
          //Collections.sort(connection);
          for (Integer c : connection) {
              if (!visited[c]) {
                  visited[c] = true;
                  q.add(c);
              }
          }
      }

      System.out.println();
  }
}