보라코딩

백준 자바 :: DFS와 BFS 본문

백준(java)

백준 자바 :: DFS와 BFS

new 보라 2024. 7. 4. 19:01

 

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

public class Main {

    static ArrayList<Integer>[] list; // 리스트의 배열
    static boolean[] visited;

    public static void main(String[] args) throws IOException{
   
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int start = Integer.parseInt(st.nextToken());

        list = new ArrayList[N+1];

        for (int i = 1; i <= N; i++){
            list[i] = new ArrayList<Integer>();
        }

        for (int i = 0; i < M; i++){
            st = new StringTokenizer(br.readLine());

            int first = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());

            list[first].add(end);
            list[end].add(first);
        }

        // 주의 sort (번호 작은 것부터)
        for(int i = 1; i <= N; i++){
            Collections.sort(list[i]);
        }

        visited = new boolean[N+1];
        DFS(start);

        System.out.println();

        visited = new boolean[N+1];
        BFS(start);

    }

    static void DFS(int node){
        System.out.print(node + " ");

        visited[node] = true;

        for(int num : list[node]){
            if(!visited[num]){
                DFS(num);
            }
        }
    }

    static void BFS(int node){
        Queue<Integer> q = new LinkedList<>();

        q.offer(node);
        visited[node] = true;

        while(!q.isEmpty()){
            int nowNode = q.poll();
            System.out.print(nowNode + " ");

            for(int num : list[nowNode]){
                if(!visited[num]){
                    visited[num] = true;
                    q.add(num);
                }
            }
        }
    }
}