문제 설명

문제 분석

슈도코드

구현

public class DFS와_BFS_프로그램_1260 {
    static ArrayList<Integer>[] adj;
    static boolean[] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokenizer = new StringTokenizer(bufferedReader.readLine());
        int N = Integer.parseInt(tokenizer.nextToken()); // 노드의 개수
        int M = Integer.parseInt(tokenizer.nextToken()); // 에지의 개수
        int V = Integer.parseInt(tokenizer.nextToken()); // 탐색 시작 노드

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

        for (int i = 1; i <= M; i++) {
            tokenizer = new StringTokenizer(bufferedReader.readLine());
            int s = Integer.parseInt(tokenizer.nextToken());
            int e = Integer.parseInt(tokenizer.nextToken());

            adj[s].add(e);
            adj[e].add(s);
        }

        // 노드 번호가 작은 것부터 시작해야 하므로 정렬.
        for(int i=1; i<=N; i++) {
            Collections.sort(adj[i]);
        }

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

        System.out.println();

        Arrays.fill(visited, false);
        BFS(V);
    }

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

        visited[node] = true;

        for(int i : adj[node]) {
            if(!visited[i]) {
                DFS(i);
            }
        }
    }

    private static void BFS(int node) {
        Queue<Integer> q = new LinkedList<>();
        // 시작 노드 방문 처리
        q.add(node);
        visited[node] = true;

        while(!q.isEmpty()) {
            int curNode = q.poll();
            System.out.print(curNode + " ");
            for(int i : adj[curNode]) {
                if(visited[i]) continue;

                visited[i] = true;
                q.add(i);
            }
        }
    }
}