백준 1260번 - DFS와 BFS

DFS와 BFS 문제를 한번 풀어보았습니다.

바이러스 문제를 풀고 이 문제를 푸니까 사실 DFS는 동일한 문제라고 생각들 정도로 금방 구현을 완료했습니다.

그러나 BFS는 DFS와 다르게 재귀로 구현하는 것이 아닌 큐를 활용해서 구현해야 합니다. (DFS도 STACK으로 구현 가능)

두 문제 모두 그래프를 인접 행렬로 만들어서 풀었는데 다른 블로그 자료를 찾아보니 그래프 간선이 적게 존재하면 연결 리스트로 구현하는 것이 공간 복잡도상 더 좋다고 합니다.

다음 글에는 한번 그래프 인접 행렬과 인접 리스트 구현에 대해서도 작성해보겠습니다.

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {

    static int N, M, start;
    static int map[][];
    static boolean visited[];

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        N = sc.nextInt();
        M = sc.nextInt();
        start = sc.nextInt();

        map = new int[N+1][N+1];
        visited = new boolean[N+1];

        int x,y;

        // Graph 인접행렬 만들기

        for(int i=0; i<M; i++){
            x = sc.nextInt();
            y = sc.nextInt();
            map[x][y] = map[y][x] = 1;
        }

        dfs(start);

        visited = new boolean[N+1];
        System.out.println();

        bfs(start);


    }

    public static void dfs(int start){
        visited[start] = true;
        System.out.print(start + " ");

        for(int i=1; i<visited.length; i++){
            if(map[start][i] == 1 && visited[i] == false){
                dfs(i);
            }
        }
    }

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

        while(!queue.isEmpty()) {
            int x = queue.poll();
            System.out.print(x+" ");
            for(int i=1; i<visited.length; i++){
                if(map[x][i] == 1 && visited[i] == false){
                    queue.offer(i);
                    visited[i] = true;
                }
            }
        }
    }
}