[Java] 너비 우선 탐색(BFS), 깊이 우선 탐색(DFS)이란? (개념 /코드 예제)

서론

---

이번엔 대표적인 그래프 탐색 알고리즘인  너비우선탐색과 깊이 우선 탐색에 대해 알아보려합니다. 보통 BFS, DFS라 불리며, 굉장히 많이 쓰이는 탐색 알고리즘에 대해 알아보겠습니다.

 

 

 

너비 우선 탐색(Breadth First Search)이란?

• 정점들과 같은 레벨에 있는 노드들을 먼저 탐색하는 방식을 말한다.

 

깊이 우선 탐색(Depth First Search)이란?

• 정점의 자식들을 먼저 탐색한느 방식을 말한다.

 

---

 

너비 우선 탐색 구현

---

그래프에서 보통 각 덩어리를 노드, 이어진 선을 간선 또는 엣지라 칭한다. BFS 방식에서 노드들의 간선 흐름을 정리하면 다음과 같다.

 

 

구현 방식

• 탐색 순서 (위 이미지 참고)
  
  • A - B - C - D - G - H - I - E - F - J
    • 한 단계 씩 내려가면서, 해당 노드와 같은 레벨에 있는 노드들을 먼저 순회한다.

 

너비 우선 탐색(BFS) 코드 구현

public class BFS {
    public static void main(String[] args) {
        HashMap<String, ArrayList<String>> graph = new HashMap<String, ArrayList<String>>();

        graph.put("A", new ArrayList<String>(Arrays.asList("B", "C")));
        graph.put("B", new ArrayList<String>(Arrays.asList("A", "D")));
        graph.put("C", new ArrayList<String>(Arrays.asList("A", "G", "H", "I")));
        graph.put("D", new ArrayList<String>(Arrays.asList("B", "E", "F")));
        graph.put("E", new ArrayList<String>(Arrays.asList("D")));
        graph.put("F", new ArrayList<String>(Arrays.asList("D")));
        graph.put("G", new ArrayList<String>(Arrays.asList("C")));
        graph.put("H", new ArrayList<String>(Arrays.asList("C")));
        graph.put("I", new ArrayList<String>(Arrays.asList("C", "J")));
        graph.put("J", new ArrayList<String>(Arrays.asList("I")));

        System.out.println(bfsFunc(graph, "A"));
    }

    private static ArrayList<String> bfsFunc(HashMap<String, ArrayList<String>> graph, String startNode) {

        //방문한 노드 List
        ArrayList<String> visited = new ArrayList<String>();

        //방문 필요한 노드 List
        ArrayList<String> needVisit = new ArrayList<String>();

        needVisit.add(startNode);

        while(needVisit.size() > 0){
            //BFS는 큐의 구조를 갖는다.
            String node = needVisit.remove(0);

            //방문 리스트에 없는 노드면 추가.
            if(!visited.contains(node)){
                visited.add(node);
                needVisit.addAll(graph.get(node));
            }
        }

        return visited;
    }
}

결과값

 

 

Logic Comment

Hashmap인 graph에 해당 노드들을 넣은 후 노드마다 연결되어있는 value들을 넣어준 후 graph와 시작 node를 받아 탐색이 시작된다.

 

(** HashMap은 키와 값을 저장하는 자료 구조로, 내부에서 해쉬 함수를 통해 키에대한 값을 빠르게 검색 할 수 있기에 사용하였다.)

 

BFS는 큐 자료구조를 사용하기에 while문이 돌면서 선입선출 구조로 node에 needvisit의 값을 넣은 후 contains 함수를 통해 이미 방문한 변수를 관리하는 visited를 검사한다. 

 

만약 visited에 node의 값이 없다면 visited에 추가해주고, needvisit에 다음 노드들을 추가해준다.

 

이렇게 해서 마지막 main에서 해당 노드들을 탐색하게끔 하여 마무리지었다. 

 

---

 

깊이 우선 탐색 구현

---

코드 구현에 앞서 너비 우선 탐색과 다른점은 스택을 사용한다는 것이다. 이 점을 제외한 나머지 부분은 모두 동일하다. 그렇기에 BFS를 잘 이해한다면 DFS는 오히려 더 쉽게 느껴질 것이라 생각한다.

 

구현 방식

• 탐색 순서 (위 이미지 참고)
  
  • A - C - I - J - H - G - B - D - F - E
    
    • 한 노드의 자식을 타고 끝까지 순회한 후, 다시 돌아와 다른 형제들의 자식을 타고 내려가며 순회한다.

 

깊이 우선 탐색(DFS) 코드 구현

public class DFS {
    public static void main(String[] args) {
        HashMap<String, ArrayList<String>> graph = new HashMap<String, ArrayList<String>>();
        graph.put("A", new ArrayList<String>(Arrays.asList("B", "C")));
        graph.put("B", new ArrayList<String>(Arrays.asList("A", "D")));
        graph.put("C", new ArrayList<String>(Arrays.asList("A", "G", "H", "I")));
        graph.put("D", new ArrayList<String>(Arrays.asList("B", "E", "F")));
        graph.put("E", new ArrayList<String>(Arrays.asList("D")));
        graph.put("F", new ArrayList<String>(Arrays.asList("D")));
        graph.put("G", new ArrayList<String>(Arrays.asList("C")));
        graph.put("H", new ArrayList<String>(Arrays.asList("C")));
        graph.put("I", new ArrayList<String>(Arrays.asList("C", "J")));
        graph.put("J", new ArrayList<String>(Arrays.asList("I")));

        System.out.println(dfsFunc(graph, "A"));
    }

    private static ArrayList<String> dfsFunc(HashMap<String, ArrayList<String>> graph, String startNode){
        ArrayList<String> visited = new ArrayList<String>();
        ArrayList<String> needVisit = new ArrayList<String>();

        needVisit.add(startNode);

        while(needVisit.size() > 0){
            //BFS와 다르게 DFS는 스택 구조이다.
            String node = needVisit.remove(needVisit.size() - 1);

            if(!visited.contains(node)){
                visited.add(node);
                needVisit.addAll(graph.get(node));
            }
        }

        return visited;
    }
}

결과 값

코드를 봐도 알겠지만 BFS와 다른점은 node를 구할 때 스택형식으로 구하는 것 외에는 다른점이 없으므로 로직에 대한 설명은 생략하겠다.

 

---

 

마무리

---

그래프 탐색 알고리즘은 생각보다 간단한 구조라 생각이 들지만 이러한 로직을 갖고 추 후 알고리즘 문제를 풀땐 꽤나 헷갈릴거같은 생각이 든다. 그렇기에 기본기를 보다 더 확실하게 잡고가야 할 것 같다.