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

devdo·2022년 4월 20일

BFS DFS

자료구조및알고리즘

목록 보기

6/8

그래프와 트리

그래프(graph)

정점(node or vertex)과 그 정점을 연결하는 간선(edge)로 이루어진 자료구조의 일종
그래프를 탐색한다는 것은 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것

트리

아주 간단한게만 말하자면, 그래프 중에서 방향성이 있는 비순환 그래프, 계층적으로 구성된 그래프이다.

루트노드, 내부노드, 리프노드 등으로 구성되며 V-1 = E 등의 특징이 있다.

그래프의 탐색의 목적은 하나의 정점에서 시작하여 그래프의 모든 정점들을 한 번씩 방문(탐색)하는 것이다.

그래프의 데이터는 배열처럼 정렬이 되어 있지 않다.

그래프에서 원하는 자료를 찾으려면, 하나씩 모두 방문하여 찾아야 한다.

❗️그래프의 모든 정점 탐색 방법

지하철 노선도 애플리케이션에서 경로를 탐색할 때, 최단 경로나 최소 환승 등 하나의 목적에도 여러 가지 방법이 있다.
그래프의 모든 정점 탐색 방법에도 여러 가지가 있다.
그중에서 가장 대표적인 두 가지 방법, DFS와 BFS를 알아보자.

이 둘은 데이터를 탐색하는 순서만 다를 뿐, 모든 자료를 하나씩 확인해 본다는 점은 같다.

DFS(깊이우선탐색)

루트 노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 아래로 깊이있게 탐색하는 방식.

모든 노드를 방문하고자 하는 경우에 이 방법을 선택함.
깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단.
검색 속도 자체는 너비 우선 탐색에 비해 느리다.

단점

재귀함수를 이용하기 때문에, 함수 호출 비용(stack을 사용하기 때문에)이 추가로 들어간다.
재귀 깊이가 지나치게 깊어지면 메모리 비용을 예측하기 어렵다. => 스택오버플로우가 발생할 수 있음.
최단 경로를 알 수 없다.

BFS(너비우선탐색)

루트 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방식.
queue를 이용하여 구현, 출발점을 먼저 큐에 넣고 다음로직을 반복

1) 큐에 저장된 정점을 하나 Dequeue한다.
2) Dequeue된 정점과 연결된 모든 정점을 큐에 넣는다.
3) 큐가 비어있다면 반복을 종료한다.

시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법
주로 두 노드 사이의 ⭐️최단 경로⭐️를 찾을 때 사용한다.

단점

DFS에 비해 코드 구현이 어렵다.
모든 지점을 탐색할 경우를 대비해,
큐의 메모리에 미리 준비되어 있어야 한다.

DFS, BFS의 시간 복잡도

두 반식 모두 조건 내의 모든 노드를 검색한다는 점에서 시간 복잡도는 동일하다.
N=노드, E=간선 일 때,

인접 리스트 : O(N+E)
인접 행렬 : O(N^2)

일반적으로 간선(E)의 크기가 N^2에 비해 상대적으로 적기에 인접 리스트 방식이 효율적이다.

왜 DFS는 최단경로를 보장못해?

예를 들어, A와 B사이의 거리를 구해야 한다. 두 가지 방식으로 했을 때의 차이?

DFS : A부터 B까지 모든 경로를 다 봐야 한다.
BFS : A와 가까운 곳부터 탐색을 시작한다.

DFS는 하나의 정점에서 계속 파고든다. 가까운 한명에서 계속 파고들어서 아니면 다시 돌아가!! 이런 개념
BFS는 나랑 연결된 애들은 일단 다 본다. 없으면 걔네랑 또 연결된 애들 본다!

그러니 최단 경로라는 문제에서 DFS는 최적해를 보장 못하는 게 맞다!

DFS, BFS 활용한 문제 유형

1) 그래프의 모든 정점을 방문하는 것이 주요한 문제
단순 모든 정점 방문이라면 DFS, BFS 어느 것을 사용해도 상관없다.

2) 경로의 특징을 저장해둬야 하는 문제 => 메모제이션
각 정점에 숫자가 적혀있고 a~b까지 가는 경로를 구하는 데, 경로에 같은 숫자가 있으면 안 된다는 문제 등, 각각의 경로마다 특징을 저장해둬야 할 때는 DFS를 사용한다. (BFS는 경로의 특징을 갖지 못한다)

3) 최단 거리를 구해야 하는 문제
미로 찾기 등, 최단 거리 일때는 BFS가 유리하다.
DFS의 경우, 처음 발견되는 답이 최단 거리가 아닐 수도 있지만 BFS는 너비 우선으로 찾기때문에 최단 거리를 여러개 받아서 Math.min()으로 비교해서 구해줄 수 있따.

+) 검색 대상 그래프가 정말 크다면 DFS
+) 검색 대상 규모가 크지 않고, 검색 시작 시점으로부터 원하는 대상이 별로 멀지 않다면 BFS

실제 코드 구현

BFS

먼저 DFS & BFS와 방문을 확인하는 배열에 현재까지의 거리를 저장한다.

✅풀이

큐에 시작 노드를 add()한다.

큐에서 노드를 poll()한다.

꺼낸 노드 상하좌우로 이동할 수 있는지 확인한다.이동가능하면
1) 노드를 추가한다.
2) 추가한 노드의 이동거리 = 현재 노드의 이동거리 + 1 (isVisit배열의 값이 0인 경우는 갈 수 없는 길이다.)

큐에 값이 존재하지 않을 때까지 2, 3을 반복한다.

import java.util.*;
class Main {
    static int n, m, answer=0;
    static ArrayList<ArrayList<Integer>> graph;
    static int[] ch, dis;
    public void BFS(int v){	// v : 현재 정점
        // 초기화
        ch[v]=1;
        dis[v]=0;
        
        Queue<Integer> queue=new LinkedList<>();
        queue.offer(v);
        
        while(!queue.isEmpty()){
            // cv : 현재 정점
            int cv=queue.poll();
            for(int nv : graph.get(cv)){
                // ch: 방문체크, 방문 안한 정점만 방문
                if(ch[nv]==0){
                    ch[nv]=1;
                    queue.offer(nv);
                    dis[nv]=dis[cv]+1; // dis[nv] 다음 거리
                }
            }
        }
    }

    public static void main(String[] args){
        Main T = new Main();
        Scanner kb = new Scanner(System.in);
        n=kb.nextInt();	// 정점의 갯수
        m=kb.nextInt();	// 간선의 갯수
        graph=new ArrayList<ArrayList<Integer>>();
        for(int i=0; i<=n; i++){
            graph.add(new ArrayList<Integer>());
        }
        
        ch=new int[n+1]; 	// 방문체크배열
        dis=new int[n+1];	// 거리
        
        for(int i=0; i<m; i++){
            int a=kb.nextInt();
            int b=kb.nextInt();
            graph.get(a).add(b);
        }
        // 출발지점은 1번 정점
        T.BFS(1);
        for(int i=2; i<=n; i++){
            System.out.println(i+" : "+dis[i]);
        }
    }
}