[알고리즘 문제] 백준1206 - BFS와 DFS

문제는 간단한데, 그래프와 시작노드가 주어질 때 BFS와 DFS로 구현하는 문제이다.

간선은 [1 2], [1 3], [1 4], [2 4], [3 4]와 같이 표현되며, 이를 사용하여 행렬을 구현하였다. 행렬을 표현할 때, 간선의 방향이 양방향이라고 하였기 떄문에 x,y / y,x에 모두 체크를 해주었다.

 

import java.util.*;

public class Main {
    static boolean[][] graph = new boolean[1001][1001];
    static boolean[] visited = new boolean[1001];
    static int N; // node
    static int E; // edge

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        E = sc.nextInt();
        int start = sc.nextInt();

        int a, b, i;
        for (i = 0; i < E; i++) {
            a = sc.nextInt();
            b = sc.nextInt();

            graph[a][b] = graph[b][a] = true;
        }

        dfs(start);

        for (int j = 0; j <= N; j++) {
            visited[j] = false;
        }
        System.out.println();
        bfs(start);
    }

    static void dfs(int start) {

        System.out.print(start + " ");
        visited[start] = true;

        for (int x = 1; x <= N; x++) {
            if (graph[start][x] && !visited[x]) {
                dfs(x);
            }
        }
    }

    static void bfs(int start) {

        Queue<Integer> que = new LinkedList<Integer>();
        que.offer(start);
        visited[start] = true;
        System.out.print(start + " ");
        int val;

        while (!que.isEmpty()) {
            val = que.poll();
            for (int x = 1; x <= N; x++) {
                if (graph[val][x] && !visited[x]) {
                    que.offer(x);
                    visited[x] = true;
                    System.out.print(x + " ");
                }
            }
        }
    }
}