[JAVA] DFS & BFS 정리

 

 

📚 DFS & BFS 최종정리 

 

 

DFS : Depth First Search 깊이 우선 탐색

BFS : Breadth First Search 너비 우선 탐색

 

그래프를 탐색하기 위한 대표적인 알고리즘 DFS, BFS를 이해하기 위해서는 스택, 큐, 재귀를 먼저 알아야한다. 

 

큐(Queue)

스택과 반대로 FIFO 개념으로 먼저 들어간 것이 먼저 나가는 자료구조이다.

public class Main{
	public static void main(String[] args) {
    	Queue<Integer> Q = new LinkedList<>();
        Q.offer(1);
        Q.offer(2);
        Q.offer(3);
        Q.poll(); // 1 출력
        Q.offer(4);
        Q.poll(); // 2 출력
    }
}

 

전역 클래스 Node

DFS와 BFS에서 사용할 Node 클래스를 미리 선언하였다. 노드는 그래프의 각각의 지점이라고 생각하면 된다.

Class Node {
	int data;
    Node lt, rt;
    public Node(int val) {
    	data = val;
        lt = null;
        rt = null;
    }
}

 

A번 노드는 lt에 해당하는 B번 노드, rt에 해당하는 C번 노드가 있다. 마찬가지로 B번 노드에는 lt에 해당하는 D번 노드, rt번에 해당하는 E번 노드가 있다. 이런 식으로 Node 클래스는 val(ex: a)와 lt, rt값으로 사용될 예정이다.

 

DFS

DFS는 자기 자신을 호출하는 순환 알고리즘의 형태를 지닌다. 위에 그림처럼 0에서 1로, 1에서 3으로 갔을 때 더 이상 갈 곳이 없다면 백트랙킹BackTracking)을 해서 다시 1로 가게 된다. 이후에 방문하지 않은 4를 방문하게 되는 형태이다. 

 

흔히 미로를 많이 예시든다. 미로를 탐색할 때 해당 분기에서 갈 수 있을 떄까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서(백트랙킹) 다른 방향으로 다시 탐색을 진행하는 방식이다.

 

DFS는 대게 스택을 사용하고 모든 노드를 방문하고자 할 때 사용한다. BFS보다 더 간단하게 구현되지만 검색속도 자체는 BFS에 비해 느리다. 

 

코드로 구현해본다면?

public class DFS {
	Node root;
    public static void main(String[] args){
    	DFS tree = new DFS();
        tree.root = new Node(0);
        tree.root.lt = new Node(1);
        tree.root.rt = new Node(2);
        tree.root.lt.lt = new Node(3);
        tree.root.lt.rt = new Node(4);
        tree.root.rt.lt = new Node(5);
        tree.root.rt.rt = new Node(6);
        tree.DFS(tree.root);
    }
}

첫번째로 위 사진 처럼 트리 형식으로 노드를 구성헌다. 이후에 DFS()함수를 실행시킨다. 인자값으로 tree.root를 넣었는데 첫번째 노드 값 0 이 들어간다.

public void DFS(Node root){
	if( root == null ) return;
    else {
    	System.out.print(root.data + " ");
        DFS(root.lt);
        DFS(root.rt);
    }
}

// 0 1 3 4 2 5 6

위 그림처럼 왼쪽부터 순차적으로 깊이 우선 탐색이 실행된 것을 확인 할 수 있다.

처음에 DFS(tree.root)함수를 호출시켰다. 즉, DFS 인자값으로 0이 처음 들어온다.

 

0은 null이 아니기 때문에 else문을 타게 되고 0을 출력한 후에 DFS(root.lt)를 호출한다. 즉 0의 왼쪽 노드인 1을 호출한다. 그러면 DFS(root.rt)는 스택에 쌓이고 DFS(root.lt)를 실행한다.

 

DFS(root.lt)가 실행하면 인자값으로 1이 넘어온다. 마찬가지로 1은 null이 아니기 때문에 else문을 타게 된다. 1을 출력한 후에 DFS(root.lt)를 실행한다. 이번에도 똑같이 DFS(root.rt)는 스택에 쌓인다.

 

DFS(1의 root.lt = 3)이 실행되고 현재까지 System.out.print()로 콘솔에 출력한 것은 0 1 3 입니다. 그 다음 수행할 것은 3의 lt이다. 하지만 tree에 3의 lt값은 없다. 즉 null이기 때문에 return 된다. 이 부분이 바로 백트랙킹이다.

 

그러면 3에서 백트랙킹을 해서 1로 다시 넘어오고 스택에 쌓인 DFS(1의 root.rt = 4 )가 수행된다. 이런 로직이 계속해서 반복하여 모든 노드를 탐색한다.

 

📌 DFS는 if~else 사용

 

 

BFS

BFS는 재귀적으로 동작하지 않고 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 큐를 사용한다. 즉 선입선출원칙으로 탐색한다. 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져있는 정점을 나중에 방문하기 때문에 대게 두 노드 사이의 최단 경로를 찾을 때 주로 사용한다. 

 

( tree는 DFS와 동일하게 구성하였음 )

public class BFS {
	Node root;
    public static void main(String[] args){
    	BFS tree = new BFS();
        tree.root = new Node(0);
        tree.root.lt = new Node(1);
        tree.root.rt = new Node(2);
        tree.root.lt.lt = new Node(3);
        tree.root.lt.rt = new Node(4);
        tree.root.rt.lt = new Node(5);
        tree.root.rt.rt = new Node(6);
        tree.BFS(tree.root)
    }
}

 

public void BFS(Node root){
	Queue<Node> Q = new LinkedList<>();
    Q.offer(root);
    int L = 0;
    while(!Q.isEmpty()) {
    	int len = Q.size();
        System.out.print(L + " : ");
        for(int i=0; i<len; ++i){
        	Node current = Q.poll();
        	System.out.print(current.data + " ");
            if(current.lt != null) {
            	Q.offer(current.lt);
            }
            if(current.rt != null) {
            	Q.offer(current.rt);
            }
        }
        L++;
        System.out.println();
    }
}

 

// 0 : 0
// 1 : 1 2
// 2 : 3 4 5 6

위 그림처럼 넓이 우선 탐색이 진행된다. 

 

처음은 DFS와 똑같이 인자값으로 0이 들어온다. 그리고 큐에 0을 넣게된다. L은 레벨을 뜻하고 초기값으로 0을 세팅했다.( 레벨은 편의상 넣은 것)

 

while문은 Queue가 비어있을 때까지 반복한다. 현재 Queue에는 0하나만 들어가있기때문에 길이 len은 1이다. 반복문을 돌면서 Queue에서 첫번째 값을 꺼내오고(0이 꺼내질 것), 그 값을 출력한 후에 lt와 rt값이 있다면 Queue에 넣어준다.

 

이제는 Queue에 2개의 값(1,2)이 들어있다. 반복문을 Queue의 길이인 2만큼 돌면서 하나씩 꺼내서 값을 출력해주고 이번에도 lt와 rt 값이 있다면 Queue에 넣어준다.

 

쉽게 말해 0일 때 1,2를 큐에 넣어주고, 1일 때 3,4를 큐에 넣어주고, 2일 때 5,6을 큐에 넣어주는 형식이다. 그리고 들어간 순서대로 꺼내져 나오는 것이다

 

📌 BFS는 while문 사용