[알고리즘] DFS / BFS

 

 

DFS (Depth- First Search) 깊이 우선 탐색

 

루트 노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식을 말한다.

주로 재귀함수 또는 Stack 으로 구현할 수 있다. 일반적으로 재귀함수를 통해 구현한다.

탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행한다.  

BFS보다 좀 더 간단하며, 모든 노드를 방문하고자 하는 경우에 이 방법을 선택한다. 

 어떤 노드를 방문했었는지 여부를 반드시 검사해야한다.

 

➡️ 목표 노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다.

 

 

 

 

 

BFS(Breadth-First-Search) 너비 우선 탐색

 

시작 노드에서 인접한 모든 노드를 먼저 탐색한 후, 다음 레벨의 노드로 이동하여 탐색한다. 

방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료 구조인 큐를 사용하여 구현할 수 있다. 

➡️  가까운 노드부터 탐색하기 때문에 최단 경로나 최단 거리를 찾는 데 유용하다.  

 

 

 

 

1. 그래프의 모든 정점을 방문해야 하는 문제

- DFS/BFS 두가지 방법 중 어느것을 사용해도 됨.

 

2. 경로의 특징을 저장해둬야 하는 문제

- 각각의 경로마다 특징을 저장해두어야 할 때는 DFS를 사용한다.

 

3. 최단거리를 구하는 문제

- 미로 찾기 등 최단 거리를 구해야 할 경우 BFS가 유리하다. 

 

 

 

 

프로그래머스 LV2. 타겟 넘버

n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

 

 

재귀함수를 사용해서 반복적으로 불러온다. 

 

class Solution {
    public int solution(int[] numbers, int target) {
        int answer = 0;
        answer= dfs(0, numbers, 0, target);
        return answer;
    }

    private int dfs(int sum, int[] numbers, int index, int target){
        if (index == numbers.length){
            if (sum==target){
                return 1;
            }
            return 0;
        }
        return dfs(sum+ numbers[index],numbers, index+1, target)
            +dfs(sum-numbers[index], numbers, index+1, target);
    }
}

 

 

 

 

 

 

DFS - 재귀함수를 이용하여 구현

public static void dfs(int v) {
        if (isVisited[v] == false) {
            System.out.print(v + " ");
            isVisited[v] = true;
        }
        for (int i = 0; i < graph[v].size(); i++) {
            if (isVisited[graph[v].get(i)]) continue;
            dfs(graph[v].get(i));
        }
    }

 

 

BFS - queue를 이용하여 구현 

 public static void bfs(int root) {
        Queue<Integer> queue= new ArrayDeque<Integer>();
        queue.add(root);
        isVisited[root] = true;

        while(!queue.isEmpty()){
            int node = queue.poll();
            System.out.print(node+ " ");

            for (int i=0; i<graph[node].size(); i++){
                if (isVisited[graph[node].get(i)]==true) continue;
                queue.add(graph[node].get(i));
                isVisited[graph[node].get(i)]=true;
            }
        }
    }