[Java] baekjoon_1260 : DFS와 BFS

그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색

DFS와 BFS : Silver2

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

1260번: DFS와 BFS

 

풀이

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

public class Main {
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    static ArrayList<Integer>[] graph;
    static boolean[] visited;

    public static void main(String[] args) throws IOException {

      StringTokenizer st = new StringTokenizer(br.readLine());
      int N = Integer.parseInt(st.nextToken()); // 정점의 개수
      int M = Integer.parseInt(st.nextToken()); // 간선의 개수
      int V = Integer.parseInt(st.nextToken()); // 시작 정점 번호

      // 그래프 초기화
      graph = new ArrayList[N + 1];
      for (int i = 1; i <= N; i++) {
        graph[i] = new ArrayList<>();
      }

      // 간선 정보 입력
      for (int i = 0; i < M; i++) {
        st = new StringTokenizer(br.readLine());
        int from = Integer.parseInt(st.nextToken());
        int to = Integer.parseInt(st.nextToken());
        graph[from].add(to);
        graph[to].add(from); // 양방향 간선
      }

      // 각 정점의 인접 정점 리스트 정렬 (번호가 작은 것부터 방문하기 위함)
      for (int i = 1; i <= N; i++) {
        Collections.sort(graph[i]);
      }

      // DFS와 BFS 수행 및 결과 출력
      visited = new boolean[N + 1];
      StringBuilder dfsRet = new StringBuilder();
      dfs(V, dfsRet);
      bw.write(dfsRet.toString() + "\n");

      visited = new boolean[N + 1];
      StringBuilder bfsRet = new StringBuilder();
      bfs(V, bfsRet);
      bw.write(bfsRet.toString() + "\n");

      br.close();
      bw.close();
    }

  public static void dfs(int v, StringBuilder ret) {
    visited[v] = true;

    ret.append(v).append(" ");

    for (int next : graph[v]) {
      if (!visited[next]) {
        dfs(next, ret);
      }
    }
  }

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

    while (!queue.isEmpty()) {
      int current = queue.poll();
      ret.append(current).append(" ");

      for (int next : graph[current]) {
        if (!visited[next]) {
            visited[next] = true;
            queue.offer(next);
        }
      }
    }
  }
}

 

DFS를 수행하는 메서드

ㄴ public static void dfs(int v, StringBuilder ret) => DFS를 수행하는 메서드이다.

    ㄴ 시작 노드 v와 결과를 저장할 StringBuilder ret을 인자로 받는다.
ㄴ visited[v] = true; => 방문한 노드를 표시한다.
ㄴ ret.append(v).append(" "); => 결과를 저장할 StringBuilder에 현재 노드를 추가한다.
ㄴ for (int next : graph[v]) { ... } => 현재 노드와 연결된 이웃 노드를 탐색한다.

    ㄴ 이웃 노드 중 방문하지 않은 노드가 있다면, 해당 노드로 DFS를 재귀적으로 호출한다.

 

BFS를 수행하는 메서드

ㄴ public static void bfs(int v, StringBuilder ret) => BFS를 수행하는 메서드이다.

     ㄴ 시작 노드 v와 결과를 저장할 StringBuilder ret을 인자로 받는다.
ㄴ Queue<Integer> queue = new LinkedList<>(); => BFS 탐색을 위한 큐를 선언한다.
ㄴ visited[v] = true; => 시작 노드를 방문한 것으로 표시한다.
ㄴ queue.offer(v); => 시작 노드를 큐에 추가한다.
ㄴ while (!queue.isEmpty()) { ... } => 큐가 빌 때까지 반복하며, 큐에서 노드를 꺼내어 이웃 노드를 탐색한다.
ㄴ for (int next : graph[current]) { ... } => 현재 노드와 연결된 이웃 노드를 탐색한다.

     ㄴ 이웃 노드 중 방문하지 않은 노드가 있다면, 해당 노드를 큐에 추가하여 다음에 탐색할 노드로 저장한다.

 

 

 

DFS (깊이 우선 탐색)

DFS는 그래프나 트리에서 한 노드로부터 시작하여 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 알고리즘이다.

한 노드의 자식들을 끝까지 탐색한 후, 다시 돌아와서 다른 자식을 탐색하는 방식이다.

 

시작 노드에서 출발하여 이웃한 노드를 하나씩 탐색하며, 해당 노드의 자식 노드로 이동하여 깊이 우선으로 탐색한다.

더 이상 자식이 없는 노드에 도달하면 이전 단계의 노드로 돌아가서 다른 이웃 노드를 탐색합니다. 이를 반복하여 전체 그래프를 탐색한다.

BFS (너비 우선 탐색)

BFS는 그래프나 트리에서 한 노드로부터 시작하여 인접한 모든 노드를 우선적으로 탐색하는 알고리즘이다.

시작 노드에서 인접한 노드를 모두 방문한 후에 다음 노드로 이동한다.

 

시작 노드에서 출발하여 이웃한 노드를 하나씩 탐색하며, 해당 노드의 이웃 노드를 큐에 추가하여 다음에 탐색할 노드로 저장한다.

이후 큐에서 노드를 하나씩 꺼내서 탐색을 반복하며, 방문한 노드는 다시 큐에 추가하지 않는다.