백준 1260. DFS와 BFS :: 돼지개발자

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

"DFS와 BFS 기초"

가장 기초적인 DFS와 BFS 탐색 문제이다. DFS는 깊이 우선 탐색, BFS는 너비 우선 탐색이다.

해당 문제에서는 인접행렬을 가지고 그래프의 연결 상태를 나타내었다. 하지만 노드의 개수가 많아진다면, 제한된 메모리 내에서 

인접 행렬을 만들기 제한되기 때문에, 인접리스트를 만들어서 처리할 수도 있다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
class Main {
 
    static int N,M,V;
    static int[][] adj;
    static boolean[] visited;
    static Queue<Integer> q = new LinkedList<>();
    static StringBuffer sb = new StringBuffer();
    
    public static void main (String[] args) throws IOException {
        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());
        
        adj = new int [N+1][N+1];
        visited = new boolean[N+1];
        
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            adj[a][b] = adj[b][a] = 1;
        }
        
        visited[V] = true;
        dfs(V);
        sb.append("\n");
        visited = new boolean[N+1];
        bfs();
        
        System.out.println(sb.toString());
    }
    
    static void dfs(int node) {
        sb.append(node+" ");
        for (int i = 1; i <= N; i++) {
            if(visited[i] || adj[node][i] == 0) continue;
            visited[i] = true;
            dfs(i);
        }
    }
    
    static void bfs() {
        visited[V] = true;
        q.add(V);
        
        while(!q.isEmpty()) {
            int cur = q.poll();
            sb.append(cur+" ");
            
            for (int i = 1; i <= N; i++) {
                if(visited[i] || adj[cur][i] == 0) continue;
                visited[i] = true;
                q.add(i);
            }
        }
    }
}