Baekjoon | Q.1260 - DFS와 BFS

1260번: DFS와 BFS

DFS와 BFS를 이용하여 그래프를 탐색하는 과정을 출력하는 문제이다.

 

import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Scanner;

class Main {
  static int n, m, v;
  static boolean[][] linked;
  static boolean[] visit;
  static StringBuilder sb = new StringBuilder();

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    n = sc.nextInt();
    m = sc.nextInt();
    v = sc.nextInt();
    
    visit = new boolean[n];
    linked = new boolean[n][n];
    
    for (int i = 0; i < m; i++) {
      int node1 = sc.nextInt();
      int node2 = sc.nextInt();
      // 양방향 연결!
      linked[node1-1][node2-1] = true;
      linked[node2-1][node1-1] = true;
    }

    sb.append(v + " ");
    visit[v-1] = true;
    dfs(1, v);
    System.out.println(sb.toString());  // 출력
    
    // 초기화
    sb.delete(0, sb.length());
    visit = new boolean[n];
    visit[v-1] = true;

    bfs();
    System.out.println(sb.toString());
  }

  static void dfs(int depth, int before) {
    if(depth == n) return;

    for (int i = 0; i < n; i++) {
      if(linked[before-1][i] && !visit[i]) {
        visit[i] = true;
        sb.append((i+1) + " ");
        dfs(depth + 1, i + 1);
      }
    }
      
  }

  static void bfs() {
    Queue<Integer> qu = new ArrayDeque<Integer>();
    qu.add(v);  // 시작할 정점 대기열에 추가
    
    while(!qu.isEmpty()) { // 큐가 완전히 비어있을 때까지 루프
      int el = qu.poll();  // 큐의 맨앞 요소를 꺼낸다.
      sb.append(el + " ");  // 출력해줄 빌더에 담는다.

      for (int i = 0; i < n; i++) {
        if(linked[el-1][i] && !visit[i]) {
          visit[i] = true;  // 방문여부 추가!
          qu.add(i+1);  // 방문한 적 없는 노드의 이웃을 전부 큐에 추가
        }
      }
    }
  }
}

 

 그래프는 인접 행렬방식으로 나타냈고 DFS는 재귀를, BFS는 큐를 이용하여 구현하였다.