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

---

DFS 기본

• 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘(최대한 멀리 있는 노드를 우선적으로 탐색하는 방식)
• 특정한 경로로 탐색하다가 특정한 상황에서 최대한 깊숙히 들어가서 노드를 방문한 후, 다시 돌아가 다른 경로로 탐색하는 알고리즘
• 재귀함수, 스택(Stack) 자료구조를 이용해 구현

---

장단점

장점

1. BFS 에 비해 저장공간의 필요성이 적고, 백트래킹을 해야하는 노드들만 저장해주면 됨
2. 찾아야하는 노드가 깊은 단계에 있고, 좌측에 있을 수록 BFS 보다 유리함

단점

1. 답이 아닌 경로가 매우 깊을 경우, 그 경로에 깊이 빠질 우려가 있음
2. 지금까지 찾은 최단경로가 끝까지 탐색 했을 때의 최단경로가 된다는 보장이 없음

---

DFS 과정

이미지 출처 https://developer-mac.tistory.com/64

1. 탐색 시작 노드를 스택에 삽입 후 방문 처리
2. 스택의 최상단 노드에 미방문 인접 노드 존재 시 해당 인접 노드를 스택에 넣고 방문처리를 함. 존재하지 않을 경우 스택에서 최상단 노드를 꺼냄
3. 2번의 과정을 반복

---

DFS 구현

void dfs(int x) {
        // 현재 노드 방문 처리
        visited[x] = true;
        System.out.print(x + " ");

        // 현재 노드와 연결된 다른 노드를 재귀적으로 방문
        for (int i = 0; i < graph.get(x).size(); i++) {
            int y = graph.get(x).get(i);
            if (!visited[y]) dfs(y);
        }
    }

---

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

---

BFS 기본

• 시작 노드에서 시작하여 인접한 노드를 먼저 탐색하는 방식, 여러 경로를 동시에 탐색 가능
• 큐(Queue) 자료구조를 이용해 구현

---

BFS 과정

이미지 출처 https://developer-mac.tistory.com/64
1. 탐색 시작 노드를 큐에 삽입한 후 방문 처리
2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중 미방문 노드를 모두 큐에 삽입 후 방문 처리
3. 2번의 과정을 반복

---

장단점

장점

1. 너비를 우선적으로 탐색하므로, 답이 되는 경로가 여러개인 경우에도 최단경로임을 보장함
2. 최단경로가 존재할 경우, 어느 한 경로가 무한히 깊어진다해도 최단경로를 반드시 찾을 수 있음
3. 노드의 수가 적고 깊이가 얕은 해가 존재할 때 유리함

단점

1. 재귀호출을 사용하는 DFS 와 달리 큐를 이용해 다음에 탐색할 노드들을 저장하므로, 노드의 수가 많을수록 불필요한 노드들까지 저장하게되므로 더 큰 저장공간이 필요
2. 노드의 수가 늘어나면 탐색해야하는 노드가 많아지므로 비현실적임

---

BFS 구현

void bfs(int start) {
        Queue<Integer> q = new LinkedList<>();
				// 1. 시작 노드를 큐에 삽입한 후 방문 처리
        q.offer(start);
        visited[start] = true;
        // 3. 2번의 과정을 반복
        while(!q.isEmpty()) {
            // 2. 큐에서 하나의 원소를 꺼냄
            int x = q.poll();
            System.out.print(x + " ");
            // 2. 해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
            for(int i = 0; i < graph.get(x).size(); i++) {
                int y = graph.get(x).get(i);
                if(!visited[y]) {
                    q.offer(y);
                    visited[y] = true;
                }
            }
        }
    }

---