[알고리즘] DFS와 BFS(백준1260문제)

DFS와 BFS

1. DFS(Depth-First-Search, 깊이우선탐색)

트리나 그래프에서 한 루트로 탐색하다가 특정 상황에서 최대한 깊숙히 들어가서 확인한 뒤 다시 돌아가 다른 루트로 탐색하는 방식이다. 대표적으로 백트래킹에 사용한다. 일반적으로 재귀호출을 사용하여 구현하지만, 단순한 스택 배열로 구현하기도 한다. 구조상 스택 오버플로우를 유의해야 한다.
갈림길이 나타날 때마다 ‘다른 길이 있다’는 정보만 기록하면서 자신이 지나간 길을 지워나간다. 그러다 막다른 곳에 도달하면 직전 갈림길까지 돌아가면서 ‘이 길은 아님’이라는 표식을 남긴다. 그렇게 갈림길을 순차적으로 탐색해 나가다 목적지를 발견하면 그대로 해답을 내고 종료한다.

• 장점
  • 단지 현 경로상의 노드들만을 기억하면 되므로 저장공간의 수요가 비교적 적다.
  • 목표노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다.
• 단점
  • 해가 없는 경로에 깊이 빠질 가능성이 있다. 따라서 실제의 경우 미리 지정한 임의의 깊이까지만 탐색하고 목표노드를 발견하지 못하면 다음의 경로를 따라 탐색하는 방법이 유용할 수 있다.
  • 얻어진 해가 최단 경로가 된다는 보장이 없다. 이는 목표에 이르는 경로가 다수인 문제에 대해 깊이우선 탐색은 해에 다다르면 탐색을 끝내버리므로, 이때 얻어진 해는 최적이 아닐 수 있다는 의미이다.

DFS-나무위키, DFS-위키백과

2. BFS(Breadth First Search, 너비우선탐색)

너비 우선 탐색(Breadth-first search, BFS)은 맹목적 탐색방법의 하나로 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법이다. 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 넓이 우선 검색을 적용한다.

• 장점
  • 출발노드에서 목표노드까지의 최단 길이 경로를 보장한다.
• 단점
  • 경로가 매우 길 경우에는 탐색 가지가 급격히 증가함에 따라 보다 많은 기억 공간을 필요로 하게 된다.
  • 해가 존재하지 않는다면 유한 그래프(finite graph)의 경우에는 모든 그래프를 탐색한 후에 실패로 끝난다.
  • 무한 그래프(infinite graph)의 경우에는 결코 해를 찾지도 못하고, 끝내지도 못한다.

BFS-위키백과

3.문제링크

https://www.acmicpc.net/problem/1260

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

public class Num1260_dfs_bfs {

    /*
     * https://www.acmicpc.net/problem/1260
     */

    public static int N, M, V;
    public static int x, y;

    public static int[][] graph = new int[1001][1001];
    public static boolean visited[] = new boolean[10001];

    public static void DFS(int V) {

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

        for(int i=1 ; i<=N ; i++) {
            if(graph[V][i] == 1 && visited[i] == false) {
                DFS(i);
            }
        }
    }

    public static void BFS(int V) {

        Queue<Integer> queue = new LinkedList<Integer>();
        int out;

        //큐에 시적점 추가
        queue.offer(V);
        visited[V] = true;
        System.out.print(V + " ");

        //큐에 값이 없을때까지 실행
        while(!queue.isEmpty()) {
            //큐에서 값 가져옴
            out = queue.poll();

            for(int i=1 ; i<= N ; i++) {
                if(graph[out][i] == 1 && visited[i] == false) {
                    //방문안한 점을 찾으면, 큐에 저장
                    queue.offer(i);
                    visited[i] = true;
                    System.out.print(i + " ");
                }
            }
        }
    }

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

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

        //두 정점을 2차원 배열에 저장
        //양방향이므로 graph[x][y] = graph[y][x] = 1 로 저장
        for(int i=1 ; i<=M ; i++) {
            x = sc.nextInt();
            y = sc.nextInt();
            graph[x][y] = graph[y][x] = 1;
        }


        DFS(V);

        //reset visited
        for(int i=1 ; i<=N ; i++){
            visited[i] = false;
        }

        System.out.println();
        BFS(V);

        sc.close();

    }

}