[DFS와 BFS] 백준,1260

• 무방향 그래프를 인접리스트로 저장하여 구현하였습니다.

public class Main {
    static int[] ch;	
    static ArrayList<ArrayList<Integer>> graph;
    // DFS
    public static void DFS(int s){
        for(int nv : graph.get(s)){
            if(ch[nv] == 0){
                ch[nv] = 1;
                System.out.print(nv+" ");
                DFS(nv);
            }
        }
    }
    // BFS
    public static void BFS(int s){
        Queue<ArrayList<Integer>> q = new LinkedList<>();
        q.offer(graph.get(s));
        while(!q.isEmpty()){
            int len = q.size();
            ArrayList<Integer> v = q.poll();
            for(int nv : v){
                if(ch[nv] == 0){
                    ch[nv] = 1;
                    System.out.print(nv + " ");
                    q.offer(graph.get(nv));
                }
            }
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int s = sc.nextInt();
        ch = new int[n+1];

        graph = new ArrayList<>();
        for(int i=0; i<=n; ++i){
            graph.add(new ArrayList<Integer>());
        }
	
    	// 무방향 그래프이기때문에, 리스트의 양쪽 모두 add 해주었습니다.
        for(int i=0; i<m; ++i){
            int x = sc.nextInt();
            int y = sc.nextInt();
            graph.get(x).add(y);
            graph.get(y).add(x);
        }

		// 문제 조건 중, 방문 가능한 노드가 여러개일 시 작은 값부터 방문하라고
        // 나와 있는데, 입력이 정렬되서 들어오지 않을 시를 대비하여
        // 리스트를 모두 오름차순으로 정렬하였습니다.
        for(ArrayList<Integer> i : graph)
            Collections.sort(i);
        ch[s] = 1;
        System.out.print(s+" ");
        DFS(s);

        System.out.println();

        ch = new int[n+1];

        ch[s] = 1;
        System.out.print(s+" ");
        BFS(s);

    }
}