[백준 1260] DFS와 BFS

 

노드의 간선의 정보를 받아 DFS, BFS 로 구현한다.

 

1. 그래프 형태로 정보를 받아 저장한다.

2. visited 배열을 만들어 방문 이력을 기록한다.

3. DFS 및 BFS 를 구현한다.

 

 

public class Main {
    
    static int n;
    static int m;
    static int a[][];
    static boolean visited[];
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        n = sc.nextInt();
        m = sc.nextInt();
        a = new int[n+1][n+1];
        visited = new boolean[n+1];
        int V = sc.nextInt();
        for(int i=0; i<m; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            a[u][v] = 1;
            a[v][u] = 1;
        }
        
        dfs(V);
        Arrays.fill(visited, false);
        System.out.println();
        bfs(V);
        sc.close();
    }
    
    public static void dfs(int x) {
        visited[x] = true;
        System.out.print(x + " ");
        for(int i=1; i<=n; i++) {
            if(a[x][i] == 1 && !visited[i]) {
                dfs(i);
            }
        }
    }
    
    public static void bfs(int x) {
        Queue<Integer> q = new LinkedList<Integer>();
        q.offer(x);
        visited[x] = true;
        while(!q.isEmpty()) {
            int curr = q.peek();
            System.out.print(q.poll() + " ");
            for(int i=1; i<=n; i++) {
                if(a[curr][i] == 1 && !visited[i]) {
                    visited[i] = true;
                    q.offer(i);
                }
            }
        }
    }
}