백준 1260 DFS와 BFS(Java)

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

1260번: DFS와 BFS

---

 

해석 및 팁

 

---

 

이 문제는 DFS와 BFS의 기본을 활용하는 문제입니다. 자세한 내용은 링크를 참조하시기 바랍니다.

https://ko.wikipedia.org/wiki/깊이_우선_탐색

깊이 우선 탐색 - 위키백과, 우리 모두의 백과사전

 

https://ko.wikipedia.org/wiki/너비_우선_탐색

너비 우선 탐색 - 위키백과, 우리 모두의 백과사전

---

 

Java 코드

 

---

import java.util.Scanner;
import java.util.Queue;
import java.util.LinkedList;

public class Main {

  static StringBuilder sb;
  static int n;
  static int m;
  static int v;
  static boolean[][] arr;
  static boolean[] visit;
  static Queue<Integer> q;


  
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    q = new LinkedList<>();
    sb = new StringBuilder();
    
    n = sc.nextInt();
    m = sc.nextInt();
    v = sc.nextInt();

    arr = new boolean[n+1][n+1];
    visit = new boolean[n+1];

    for(int i = 0; i < m; i++) {
      int a = sc.nextInt();
      int b = sc.nextInt();
      arr[a][b] = arr[b][a] = true;
    }

    dfs(v);
    sb.append("\n");
    visit = new boolean[n+1];
    bfs(v);
    
    System.out.println(sb);
  }

  static void dfs(int num) {
    visit[num] = true;
    sb.append(num+" ");
    for(int i = 1; i <= n; i++) {
      if(visit[i] == false && arr[num][i]) dfs(i);
    }
  }

  static void bfs(int num) {
    visit[num] = true;
    q.add(num);
    while(!q.isEmpty()) {
      num = q.poll();
      sb.append(num+" ");
      for(int i = 1; i <= n; i++) {
        if(visit[i] == false && arr[num][i]) {
          q.add(i);
          visit[i] = true;
        }
      }
    }
  }
  
}