백준 - 그래프와 순회 1260 DFS와 BFS문제 / 문제풀이, 해설 링크

https://www.youtube.com/watch?v=d3R1s_OmwAk 

DFS와 BFS에 대한 해설은 이 영상을 참조하는게 좋을 것 같다.

나도 접근 방법을 아예 몰랐기 때문에 이 영상으로 공부했다.

 

DFS는 깊이 우선, BFS 너비 우선

 

DFS는 한 곳만 죽어라 파고, BFS는 여러개를 골고루 판다는 느낌이다

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
 
public class Main {
    public static int n, m, v;
    public static boolean[] visited;
    public static boolean[][] dp;
    public static List<Integer> q;
    public static void main(String[] args) throws IOException {
        // 1. input
        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()); // 시작 번호
 
        visited = new boolean[n + 1];
        dp = new boolean[n + 1][n + 1];
 
 
        for (int i = 1; i <= m; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
 
            dp[a][b] = true;
            dp[b][a] = true;
        }
 
        dfs(v);
        System.out.println();
 
        bfs();
 
    }
 
    public static void dfs(int v) {
        visited[v] = true;
        System.out.print(v + " ");
 
        for (int i = 1; i <= n; i++) {
            if (!visited[i] && dp[v][i]) {
                dfs(i);
            }
        }
    }
 
    public static void bfs() {
        q = new ArrayList<>();
        visited = new boolean[n + 1];
 
        q.add(v);
        visited[v] = true;
 
        while (!q.isEmpty()) {
            int idx = q.remove(0);
            System.out.print(idx + " ");
 
            for (int i = 1; i <= n; i++) {
                if (!visited[i] && dp[idx][i]) {
                    q.add(i);
                    visited[i] = true;
                }
            }
        }
    }
}