[Java]백준 1260번 :: DFS와 BFS

백준 온라인 저지 1260번 - DFS와 BFS

Java 알고리즘 문제풀이

풀이

그래프를 이용한 경로탐색 알고리즘에 대표적으로 2가지가 존재한다.

• DFS (깊이 우선 탐색)
• BFS (너비 우선 탐색)

코딩테스트에서 대표적으로 출제되는 문제라 알아두는 것이 좋은 알고리즘인데, 이 문제는 이 두가지 알고리즘을 연습하기에 좋은 문제이다.

실제 코딩테스트에서는 경로를 찾는 문제에서 많이 쓰인다.

DFS 알고리즘에 경우 두 가지 방법으로 풀 수 있는데, 

첫 번째로 스택을 이용하는 것

두 번째로 재귀함수를 이용하는 것인데, 재귀함수를 이용하는 것이 가장 보편적이고 짧은 코드를 작성할 수 있다.

BFS 알고리즘은 Queue를 사용해서 문제를 해결하면 된다.

import java.util.*;

public class Beak1260 {
    static ArrayList<Integer>[] list;
    static int n;
    static boolean[] check;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        int m = sc.nextInt();
        int start = sc.nextInt();

        list = new ArrayList[n + 1];

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

        for (int i = 0; i < m; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();

            list[u].add(v);
            list[v].add(u);
        }
        for (int i = 1; i < n + 1; i++) {
            Collections.sort(list[i]);
        }
        check = new boolean[n + 1];
        dfs(start);
        System.out.println();

        check = new boolean[n + 1];
        bfs(start);
        System.out.println();

        sc.close();
    }

    private static void dfs(int x) {
        if (check[x]) {
            return;
        }

        check[x] = true;
        System.out.print(x + " ");
        for (int y : list[x]) {
            if (!check[y])
                dfs(y);
        }

    }

    private static void bfs(int start) {
        Queue<Integer> queue = new LinkedList<Integer>();
        queue.add(start);
        check[start] = true;

        while (!queue.isEmpty()) {
            int x = queue.poll();
            System.out.print(x + " ");
            for (int y : list[x]) {
                if (!check[y]) {
                    check[y] = true;
                    queue.add(y);
                }
            }
        }
    }
}