[JAVA] 백준 1260번 : DFS와 BFS

1260번: DFS와 BFS

문제

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램.

단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

 

입력

- 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V

- 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호

어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

 

출력

- 첫째 줄에 DFS를 수행한 결과

- 다음 줄에는 BFS를 수행한 결과를 출력

V부터 방문된 점을 순서대로 출력하면 된다.

 

풀이

 

DFS(깊이우선) 는 재귀나 스택으로 (보통 재귀를 사용한다), BFS(너비우선)는 큐로 해결한다.

간선들이 연결되어 있는지 아닌지 판단할 때, 인접행렬이나 인접리스트를 이용한다.

인접행렬 사용시 시간 복잡도 : O(V^2)
인접리스트 사용시 시간 복잡도 : O(V+E)
이므로 인접리스트를 사용하여 푸는 것이 좋다. 인접행렬은 연결되어있으면 1, 연결되어있지 않으면 0 으로 처리하는 것으로 구현과 이해가 쉽다는 장점이 있지만, 정점의 개수(여기선 N)가 늘면 늘수록 탐색하는 시간이 오래걸린다는 단점이 있다.양방향 간선이기 때문에 ArrayList<ArrayList>를 사용해서 하나의 간선을 입력받을 시 반대 간선도 같이 저장 시켜주어야한다.

밑에서는 인접리스트로 구현

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class bj1260 {
  static private List<List<Integer>> adjacencyList;
  static boolean[] visited;

  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]); // 탐색 시작할 정점

    visited = new boolean[N + 1];
    adjacencyList = new ArrayList<>(N + 1);
    for (int i = 0; i <= N; i++) {
      adjacencyList.add(new ArrayList<>());
    }

    // 그래프 초기화
    for (int i = 0; i < M; i++) {
      input = br.readLine().split(" ");
      int a = Integer.parseInt(input[0]);
      int b = Integer.parseInt(input[1]);
      adjacencyList.get(a).add(b);
      adjacencyList.get(b).add(a);
    }

    for (int i = 1; i <= N; i++) {
      Collections.sort(adjacencyList.get(i));
    }

    dfs(V);
    visited = new boolean[N + 1];
    System.out.println();
    bfs(V);
  }

  public static void dfs(int v) {
    visited[v] = true;
    System.out.print(v + " ");

    for (int neighbor : adjacencyList.get(v)) {
      if (!visited[neighbor]) {
        dfs(neighbor);
      }
    }
  }

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

    while (!queue.isEmpty()) {
      int currentV = queue.poll();
      System.out.print(currentV + " ");

      List<Integer> neighbors = adjacencyList.get(currentV);
      for (int neighbor : neighbors) {
        if (!visited[neighbor]) {
          visited[neighbor] = true;
          queue.offer(neighbor);
        }
      }
    }
  }
}