DFS와 BFS - 백준(1260, 그래프 탐색)

🎯 DFS와 BFS

DFS와 BFS - 1260, 그래프 탐색, 실버2

🧐 알고리즘[접근방법]

1. 장점의 개수로 2차원 배열 선언, 방문 여부를 판단한 1차원 배열 선언

2. 간선을 입력 받으면서 2차원 배열에 각각 넣어준다.ex) 1 2 입력 시 => 1 ➡ 2 , 2 ➡ 1

3. BFS 함수 구현

   • Integer 타입의 Queue 선언
   • 시작 index Queue에 추가 및 시작 점 방문 처리
   • 2차원 배열 탐색하면서 연결 된 점 Queue 추가 및 방문 처리

4. DFS 함수 구현(재귀)

   • 시작 index 방문 처리
   • 시작 점 시준으로 2차원 배열 탐색하면서 연결 된 점 방문 처리 및 DFS 함수 호출

👨‍💻 소스

import java.util.*;

public class Main {

  public static int[][] map;
  public static boolean[] check;
  public static StringBuilder sbDFS = new StringBuilder();
  public static StringBuilder sbBFS = new StringBuilder();
  
  public static void main(String[] args) {
    
    Scanner sc = new Scanner(System.in);
    
    int N = sc.nextInt(); // 장점의 개수
    int M = sc.nextInt(); // 간선의 개수
    int V = sc.nextInt(); // 탐색 시작 번호
    
    map = new int[N + 1][N + 1];
    for(int i = 0 ; i < M ; i++) {
      int n1 = sc.nextInt();
      int n2 = sc.nextInt();
      
      map[n1][n2] = 1;
      map[n2][n1] = 1;
    }
    
    check = new boolean[N + 1];
    DFS(V);
    check = new boolean[N + 1];
    BFS(V);
    
    System.out.println(sbDFS.toString());
    System.out.println(sbBFS.toString());
    
    sc.close();
    
  }
  
  public static void DFS(int index) {
    check[index] = true;
    sbDFS.append(index + " ");
    
    for(int i = 0 ; i < map[index].length ; i++) {
      if(map[index][i] == 1 && !check[i]) {
        check[i] = true;
        DFS(i);
      }
    }
  }
  
  public static void BFS(int index) {
    Queue<Integer> q = new LinkedList<Integer>();
    q.add(index);
    check[index] = true;
    sbBFS.append(index + " ");
    
    while(!q.isEmpty()) {
      int n = q.poll();
      
      for(int i = 1 ; i < map[n].length ; i++) {
        if(map[n][i] == 1 && !check[i]) {
          q.add(i);
          check[i] = true;
          sbBFS.append(i + " ");
        }
      }
    }
  }
![](https://media.vlpt.us/images/thehill_hannam/post/5ac90669-fc26-4a2d-9562-3cebdcc21e2e/%EB%B0%B1%EC%A4%80.png)
}

🏅 결과

📖 관련 지식