[백준] 1260번 : DFS와 BFS (DFS, BFS)

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

직접 풀기

DFS는 재귀, BFS는 Queue로 해결하자

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

public class Main {

  static StringBuilder sb = new StringBuilder();
  static boolean[] visited;
  static int[][] arr;
  static int node, line, start;
  static Queue<Integer> q = new LinkedList<>();

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

    node = Integer.parseInt(st.nextToken());
    line = Integer.parseInt(st.nextToken());
    start = Integer.parseInt(st.nextToken());

    arr = new int[node + 1][node + 1];
    visited = new boolean[node + 1];

    for (int i = 0; i < line; i++) {
      StringTokenizer str = new StringTokenizer(br.readLine());
      int a = Integer.parseInt(str.nextToken());
      int b = Integer.parseInt(str.nextToken());
      // 양방향
      arr[a][b] = arr[b][a] = 1;
    }

    // DFS
    dfs(start);
    sb.append("\n");

    // BFS
    visited = new boolean[node + 1]; // 방문 기록 초기화
    bfs(start);

    // 출력
    System.out.println(sb);
  }

  public static void dfs(int start) {
    // 방문 체크
    if (visited[start]) {
      return;
    }

    // 방문
    visited[start] = true;
    sb.append(start + " ");

    for (int i = 1; i <= node; i++) {
      if (arr[start][i] == 1 && !visited[i]) {
        dfs(i);
      }
    }
  }

  public static void bfs(int start) {
    q.add(start);
    visited[start] = true;

    while (!q.isEmpty()) {
      start = q.poll();
      sb.append(start + " ");

      for (int i = 1; i <= node; i++) {
        if (arr[start][i] == 1 && !visited[i]) {
          q.add(i);
          visited[i] = true;
        }
      }
    }
  }
}

다시 이해해 보기

그래프 탐색 알고리즘인 DFS(Depth-First Search)와 BFS(Breadth-First Search)를 구현한 것입니다. 그래프는 node개의 노드와 line개의 간선으로 구성됩니다. 주어진 시작점에서 DFS와 BFS를 수행하고, 그 결과를 출력하는 프로그램입니다. 아래에서 각 부분을 이해하기 쉽게 설명드리겠습니다.