DFS/BFS

DFS와 BFS는 그래프(정점node와 간선edge로 이루어진 자료구조) 탐색 방법입니다.

문제 풀이는 백준을 이용했습니다.

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

public class Main {
    
    static int N,M,V;
    static int[][] arr;
    static boolean[] checked;
    static Queue<Integer> q = new LinkedList<>();
    static StringBuilder sb = new StringBuilder();
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        V = Integer.parseInt(st.nextToken());
        
        arr = new int[N+1][N+1];
        checked = new boolean[N+1];
        
        for(int i=0; i<M; 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(V);
        sb.append("\n");
        
        // bfs : Queue 이용
        checked = new boolean[N+1];
        bfs(V);
        
        System.out.println(sb);
    }
    
    public static void dfs(int num) {
        checked[num] = true;
        sb.append(num + " ");
        for(int i=0; i<=N; i++) {
            // 간선으로 이어져 있고, 방문하지않은 노드일 때
            if(arr[num][i] == 1 && !checked[i]) { 
                dfs(i);
            }
        }
    }
    
    public static void bfs(int num) {
        checked[num] = true;
        q.add(num);
        
        while(!q.isEmpty()) {
            num = q.poll();
            sb.append(num + " ");
            
            for(int i=1; i<=N; i++) {
                // 간선으로 이어져있고, 방문하지 않은 노드일 때
                if(arr[num][i] == 1 && !checked[i]) {
                    q.add(i);
                    checked[i] = true;
                }
            }
        }
    }
    
    
}

---

1️⃣ 간선 이어짐 표현하기

  arr = new int[N+1][N+1];
  checked = new boolean[N+1];
  
  for(int i=0; i<M; 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;
  }
        

• 2차원 배열로 정점에 해당하는 배열의 인덱스가 1일때는 이어진 것, 0일때는 이어지지 않은 것으로 표현합니다.
• 인덱스를 0이 아닌 번호에 맞추어 표현하기 위해 N+1개로 배열 생성하였습니다.

 

2️⃣ DFS

public static void dfs(int num) {
    checked[num] = true;
    sb.append(num + " ");
    for(int i=1; i<=N; i++) {
        // 간선으로 이어져 있고, 방문하지않은 노드일 때
        if(arr[num][i] == 1 && !checked[i]) { 
            dfs(i);
        }
    }
}

• 깊이우선탐색
• 스택, 재귀함수 이용
  • num행의 열을 모두 탐색하면서, i번째 행이 조건에 맞으면 num탐색하다가도 i번째 행부터 다시 모두 탐색한다. → 점점 깊이 들어가게 됩니다.

 

3️⃣ BFS

public static void bfs(int num) {
    checked[num] = true;
    q.add(num);
    
    while(!q.isEmpty()) {
        num = q.poll();
        sb.append(num + " ");
        
        for(int i=1; i<=N; i++) {
            // 간선으로 이어져있고, 방문하지 않은 노드일 때
            if(arr[num][i] == 1 && !checked[i]) { 
                q.add(i);
                checked[i] = true;
            }
        }
    }
}

• 너비우선탐색
• 큐 이용 (선입 선출 → 깊이가 아닌 너비 우선 탐색을 하게 됩니다)
  
  • num행의 열을 모두 탐색(for문)한 뒤, q에 담긴 숫자 행에 대한 열을 다시 모두 탐색합니다. → 너비 탐색