[JAVA][그래프] 백준 1260번

[JAVA] 백준 1260번 - DFS와 BFS

 

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

public class Main {

    static int N;
    static ArrayList<ArrayList<Integer>> graph;
    static BufferedWriter bw;
    static boolean[] visitedDfs;
    static boolean[] visitedBfs;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int V = Integer.parseInt(st.nextToken());

        graph = new ArrayList<>();
        visitedDfs = new boolean[N + 1];
        visitedBfs = new boolean[N + 1];

        for (int i = 0; i <= N; i++) {
            graph.add(new ArrayList<Integer>());
        }

        for (int j = 0; j < M; j++) { //초기 연결하는 두 정점 값 세팅
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            graph.get(start).add(end);
            graph.get(end).add(start);
        }

        for (int i = 0; i <= N; i++) {
            Collections.sort(graph.get(i));
        }

        dfs(V);
        bw.newLine();
        bfs(V);

        bw.flush();
        bw.close();

    }

    private static void bfs(int V) throws IOException { //Queue를 이용한 BFS

        Queue<Integer> queue = new LinkedList<>();
        queue.add(V);
        visitedBfs[V] = true;
        bw.write(V + " ");

        while (!queue.isEmpty()) {
            int value = queue.poll();

            for (int val : graph.get(value)) {
                if (visitedBfs[val] == false) {
                    queue.add(val);
                    bw.write(val + " ");
                    visitedBfs[val] = true;
                }
            }
        }
    }

    private static void dfs(int V) throws IOException { //재귀를 이용한 DFS

        bw.write(V + " ");
        visitedDfs[V] = true;

        for (int value : graph.get(V)) {
            if (visitedDfs[value] == false) {
                dfs(value);
            }
        }
    }


}

 

정답을 맞춘 풀이방법

1. ArrayList<ArrayList<>>를 사용해 그래프를 만들고 정점과 간선을 입력받음

2. Queue를 사용한 BFS(너비우선탐색)을 구현, 재귀를 사용한 DFS(깊이우선탐색)을 구현

3. 각각의 결과를 출력함.

 

※DFS의 경우 재귀대신 Stack을 사용할 수 있지만 코드가 좀 더 길어진다.