글의 목적

이전 글에서 DFS ,BFS의 개념을 알아보았습니다.
1. Java 코드를 통해 이해한 개념을 구현해보는 글입니다.
2. DFS = (Stack & 재귀함수) BFS = (Queue) 를 통해 구현해보도록 하겠습니다.
3. DFS & BFS 중 어느 것을 사용해야 하는지에 대한 기준을 알아보겠습니다.

DFS

DFS (재귀함수)

package Implementation;

import java.util.Iterator;
import java.util.LinkedList;

public class DFS_Recursion {

    private int V;
    private LinkedList<Integer>[] adj;

    //생성자

    public DFS_Recursion(int v){

        V= v;
        adj = new LinkedList[v];
        // v개의 LinkedList 선언
        for(int i = 0 ; i <v;i++){
            adj[i]= new LinkedList<>();
        }

    }

    public void addEdge(int v , int w){
        adj[v].add(w);
    }

    // DFS 함수
    // 시작노드 v
    public void DFS_Recur(int v){

        boolean visited[] = new boolean[V];
        DFSUtil(v,visited);

    }
    void DFSUtil(int v , boolean visited[]){

        // 현재 노드를 방문한 것으로 체크 (visited 의 v번째 요소를 true로)
        visited[v] =true;
        System.out.println(v+" ");

        // 방문한 노드와 인접한 모든 노드를 가지고 온다.
        Iterator<Integer> it = adj[v].listIterator();

        while(it.hasNext()){
            int n = it.next();
            // 방문하지 않은 노드면 다시 재귀를 통해 DFUtil 호출
            if(!visited[n]) DFSUtil(n,visited);
        }
    }
}

DFS(Stack)

package Implementation;

import java.util.LinkedList;
import java.util.Stack;

public class DFS_Stack {
    private int V;
    private LinkedList<Integer>[] adj;

    public DFS_Stack(int v) {

        V = v;
        adj = new LinkedList[v];
        // v개의 LinkedList 선언
        for (int i = 0; i < v; i++) {
            adj[i] = new LinkedList<>();
        }

    }

    public void addEdge(int v, int w) {
        adj[v].add(w);
    }

    public void DFS_Stk(int v) {

        boolean visited[] = new boolean[V+1];
        Stack<Integer> st = new Stack<>();

        st.push(v);
        visited[v]=true;
        while (!st.isEmpty()) {
            int vertex = st.pop();

            for (int adj_num : adj[vertex]) {
                if(!visited[adj_num]){
                    st.push(adj_num);
                    visited[adj_num]=true;
                    System.out.println(adj_num+" ");

                }
            }

        }
    }
}

BFS

BFS(Queue)

package Implementation;

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

public class BFS_Queue {

    public int V;
    public LinkedList<Integer>[] adj;

    public BFS_Queue(int v) {

        V = v;
        adj = new LinkedList[v];
        for (int i = 0; i < v; i++) {
            adj[i] = new LinkedList<>();
        }

    }

    void addEdge(int v, int w) {

        adj[v].add(w);

    }

    //시작 정점을 parameter로 받고, BFS 진행
    public void BFS_Q(int v) {

        boolean visited[] = new boolean[V + 1];
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(v);
        visited[v] = true;

        //Queue가 다 빌 때까지 돌면서 정점 탐색
        while (!queue.isEmpty()) {

            int vertex = queue.poll();

            for (int adj_num : adj[vertex]) {
                if (!visited[adj_num]) {
                    System.out.println(adj_num+" ");
                    queue.add(adj_num);
                    visited[adj_num]=true;
                }
            }
        }

    }
}

#cf) 알고리즘 구현과 문제를 풀면서 느낀점은 기본 알고리즘에서 문제에 맞게끔 변형하여 알고리즘을 사용하면 되는 것이라고 생각이 들었고, 각각 어떤 점이 유리한지, 불리한지에 대해 알아볼 필요가 있다.

DFS & BFS 사용기준

DFS

• 모든 경우를 하나하나 탐색하는 경우 (완전탐색 문 )
• 연결된 그래프 완전 탐색하는데 활용 가능
• 순열, 조합 구현에 활용

BFS

• 연결된 그래프를 완전 탐색하는데 활용
• depth 특징을 이용한 문제를 풀어야할 경우 ( ex) 최단경로 구하는 문제)

#cf) 실제로 알고리즘 문제들은 DFS,BFS 모두 가능한 경우가 많다고 하고, 문제를 풀면서 자신이 빨리 풀 수 있는 것을 선택해서 푸는 것이 중요하다고 한다.. 결론은 문제를 많이 풀어보는 것이 중요하다~