[java] 깊이 우선 탐색 (DFS)

깊이 우선 탐색(Deapth First Search)는 앞서 정리한 너비 우선 탐색과 반대로 깊이를 우선 탐색하는 방식이다.

즉, 하나의 child노드를 방문하면 그 child노드로 계속해서 파고드는 것이다.

 

DFS와 BFS를 비교하면 다음과 같다.

 

또한 깊이 우선 탐색은 Stack을 이용해 구성한다.

 

1. 시작할 노드를 스택에 넣는다.

2. 노드를 꺼내서 해당노드의 자식노드를 스택에 넣는다.

* 이때 이미 넣었던 노드는 다시 넣지 않는다.

3. 꺼낸 노드는 출력한다.

4. 2번과 3번을 반복해 스택이 빌때까지 진행한다.

 

 

package Search;
 
import java.util.EmptyStackException;
import java.util.LinkedList;
import java.util.NoSuchElementException;
 
class Stack<T>{
    class Node<T>{
        private T data;
        private Node<T> next;
        
        public Node(T data) {
            this.data = data;
        }
    }
    
    private Node<T> top;
    
    public T pop() {
        if(top == null) {
            throw new EmptyStackException();
        }
        
        T item = top.data;
        top = top.next;
        return item;
    }
    
    public void push(T item) {
        Node<T> t = new Node<T>(item);
        t.next = top;
        top = t;
    }
    
    public T peek() {
        if(top == null) {
            throw new EmptyStackException();
        }
        return top.data;
    }
    
    public boolean isEmpty() {
        return top == null;
    }
}
 
// 큐를 구현해 놓은 클래스이다
class Queue<T>{
    class Node<T> {
        private T data;
        private Node<T> next;
        
        public Node(T data) {
            this.data = data;
        }
    }
    
    private Node<T> first;
    private Node<T> last;
    
    public void enqueue(T item) {
        Node<T> t = new Node<T>(item);
        if(last != null) {
            last.next = t;
        }
        last = t;
        if(first == null) {
        first = last;
        }
    }
    
    public T dequeue() {
        if(first == null) {
            throw new NoSuchElementException();
        }
        T item = first.data;
        first = first.next;
        
        if(first == null) {
            last = null;
        }
        return item;
    }
    
    public T peek() {
        if(first == null) {
            throw new NoSuchElementException();
        }
        return first.data;
    }
    
    public boolean isEmpty() {
        return first == null;
    }
}
 
//그래프 클래스를 만들어 주어진 노드끼리 연결을 구현한다
class Graph{
    class Node{
        int data;
        LinkedList<Node> adjacent; //자식노드가 아닌 인접한 노드를 생성
        boolean marked; //방문 여부 확인 변수
        Node(int data){
            //생성자에서 데이터를 받고 방문여부 초기화, linkedlist 준비
            this.data = data;
            this.marked = false;
            adjacent = new LinkedList<Node>();
        }
    }
    
    Node[] nodes; //노드들의 배열 선언
    Graph(int size) {
        nodes = new Node[size];//생성자에서 받은 size만큼 배열방을 만든다
        for(int i = 0; i < size; i++) {
            nodes[i] = new Node(i); //편의상 데이터를 i로 임의설정
        }
    }
    
    //두 노드의 관계를 저장하는 메소드
    public void addEdge(int i1, int i2) {
        Node n1 = nodes[i1];
        Node n2 = nodes[i2];
        if(!n1.adjacent.contains(n2)) {
            n1.adjacent.add(n2);
        }
        
        if(!n2.adjacent.contains(n1)) {
            n2.adjacent.add(n1);
        }
    }
    
    void dfs() {
        dfs(0); // 깊이 우선 탐색을 어디부터 시작할지 정하는 것
    }
    
    void dfs(int index) {
        Node root = nodes[index]; //시작 인덱스를 받기
        Stack<Node> stack = new Stack<Node>();//스택 생성
        stack.push(root);//현재노드를 스택에 추가
        root.marked = true; //스택에 방문 여부 확인
        while(!stack.isEmpty()) { // 스택에 아무것도 없을 때까지 반복
            Node r = stack.pop(); //스택에서 데이터를 하나 꺼냄
            for(Node n : r.adjacent) { //자식노드 있는 만큼 반복
                if(n.marked == false) {//방문하지 않았던 곳만 방문 조건
                    n.marked = true; //방문하면 체크 표시
                    stack.push(n); //스택에 데이터 넣기
                }
            }
            visit(r); //빠져나온 노드 출력메소드
        }
    }
    
    void bfs() {
        bfs(0); //너비 우선 탐색도 0부터 시작설정
    }
    
    void bfs(int index) {
        Node root = nodes[index];
        Queue<Node> queue = new Queue<Node>();
        queue.enqueue(root);
        root.marked = true;
        while(!queue.isEmpty()) {
            Node r = queue.dequeue();
            for(Node n : r.adjacent) {
                if(n.marked == false) {
                    n.marked = true;
                    queue.enqueue(n);
                }
            }
            visit(r);
        }
    }
    
    void visit(Node n) {
        System.out.print(n.data + " ");
    }
    
}
 
 
public class Test {
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
/*      0
 *     /
 *   1 -- 3     7
 *   |  / | \  /
 *   | /  |   5
 *   2 -- 4    \
 *              6 - 8
 */
        Graph numbers = new Graph(9); //9개 노드 그래프 생성
        numbers.addEdge(0,1); //인접한 노드 표시
        numbers.addEdge(1,3); 
        numbers.addEdge(1,2); 
        numbers.addEdge(2,3); 
        numbers.addEdge(2,4); 
        numbers.addEdge(3,4); 
        numbers.addEdge(3,5); 
        numbers.addEdge(5,7); 
        numbers.addEdge(5,6);
        numbers.addEdge(6,8); 
        
        //numbers.dfs();
        numbers.bfs();
        
        
        
    }
 
}