[알고리즘] DFS와 BFS란?

 

1260번: DFS와 BFS

 

DFS(깊이 우선 탐색)

 

DFS는 깊이 우선 탐색으로 그래프를 탐색하는 방법이다.

탐색 순서는 다음과 같다.

 

그림을 보면 알겠지만 루트 노드에서부터 제일 깊은 곳을 먼저 찍고 옆으로 이동한다.

구현은 스택과 재귀 함수로 구현한다.

 

장점

• 목표하는 노드가 깊이 있을 경우 BFS보다 빠르게 찾을 수 있다.
• 간단하게 구현할 수 있다.

 

단점

• 속도가 BFS보다 느리다.
• 해가 없는 경로에 깊이 빠질 가능성이 있다.
• 얻어진 해가 최단 경로가 된다는 보장이 없다.

 

구현(재귀 함수)

public static void dfs(int start) {
    visit[start] = true;
    System.out.print(start + " ");
    for (int i = 0; i <= N; i++) {
        if (branch[start][i] == 1 && !visit[i]) {
            dfs(i);
        }
    }
}

시작 노드를 먼저 방문 처리를 해준다.

그리고 노드들을 돌면서 노드가 있고(여기선 1로 표기해둠) 방문하지 않았을 경우 재귀

 

BFS(넓이 우선 탐색)

 

DFS는 너비 우선 탐색으로 그래프를 탐색하는 방법이다.

탐색 순서는 다음과 같다.

 

 

루트 노드에서 레벨별로 읽기 때문에 그림에서 보면 좌측에서 우측으로 노드를 읽는다.

즉, 루트에서 자식 노드들을 저장하고, 다시 차례대로 각각의 자식 노드를 저장한다. 

그리고 모두 방문하면 탐색을 마친다.

구현은 큐로 한다.

 

장점

• 시작 노드에서 목표 노드까지 최단 경로를 보장한다.
• 최단 경로가 존재하면 깊이가 무한정이어도 답을 찾을 수 있다. (DFS는 깊게 계속 들어가기 때문에 무한정일 경우 해를 못 찾음)

 

단점

• 노드의 수가 많아질수록 메모리가 많이 필요하게 된다.

 

구현(큐)

public static void bfs(int start) {
    q = new LinkedList<>();
    q.add(start);
    visit[start] = true;
    System.out.print(start + " ");

    while (!q.isEmpty()) {
        int temp = q.poll();

        for (int i = 0; i <= N; i++) {
            if (branch[temp][i] == 1 && !visit[i]) {
                q.add(i);
                visit[i] = true;
                System.out.print(i + " ");
            }
        }
    }
}

시작 노드를 큐에 넣고 방문 처리를 해준다.

그리고 q가 빌 때까지 반복문을 돌려주면서 q에서 데이터를 poll 한다.

그리고 poll 한 값(부모 노드)의 자식이 존재하고 아직 방문하지 않았을 경우 q에 넣어주고 방문처리를 한다.