DFS & BFS

내가 보려고 씀

⭐ DFS (Depth-First Search)

깊이 우선 탐색

💡 개념

1. 넓게(wide) 탐색하기 전에 깊게(deep) 탐색
2. 모든 노드를 방문하고자 하는 경우에 이 방법을 선택
3. BFS 보다 간단
4. BFS에 비해 검색 속도 느림

💡 특징

1. 재귀함수를 이용함, 재귀함수의 코드가 훨씬 짧음
   1. 재귀함수란? 자기 자신을 호출하는 순환 알고리즘
2. 어떤 노드를 방문했었는지 여부를 반드시 검사 (검사하지 않으면 무한루프)
3. 모든 경우의 수를 탐색하고자 하는 미로 문제 같은 경우 적합 -> 미로 : 최단 경로X, 탈출 경로O

💡 구현 방법

방법 : https://codingnojam.tistory.com/44

1. 스택 : 방문하는 순서대로 정점을 스택에 쌓고, 방문이 끝나면 스택에서 pop
2. 재귀함수 : 재귀 함수를 이용하는 것이 가장 보편적이고 짧은 코드를 작성

// 재귀(Recursion) 형태로 구현
// dfs, 재귀, 인접 행렬, i 정점부터 시작
// 원소 삽입 : push()
// 원소 조회 : peek()
// 원소 뺴냄 : pop()

public static void dfs(int i) {

    visit[i] = true;

    for(int j = 1; j < n + 1; j++) {
        if(map[i][j] == 1 && visit[j] == false) {
            dfs(j);
        }

    }
}

⭐ BFS (Breadth-First Search)

너비 우선 탐색

💡 개념

1. 깊게(deep) 탐색하기 전에 넓게(wide) 탐색
2. 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색

💡 특징

1. 재귀적으로 동작하지 않음
2. 어떤 노드를 방문했었는지 여부를 반드시 검사 (검사하지 않으면 무한루프)
3. 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때

💡 구현 방법

방법 : https://codingnojam.tistory.com/41?category=1015196

1. 큐(Queue) : 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료 구조인 큐(Queue)를 사용
   즉, 선입선출(FIFO) 원칙

// bfs, 큐 사용, 인접행렬, i 정점부터 시작
// 원소 삽입 : offer(), add()
// 빼낼 원소 조회 : peek()
// 원소 빼냄 : poll(), remove()

public static void bfs(int i) {

    Queue<Integer> q = new LinkedList<>();

    q.offer(i);

    visit[i] = true;

    while(!q.isEmpty()) {
        int temp = q.poll();
        for(int j = 1; j < n + 1; j++) {
            if(map[temp][j] == 1 && visit[j] == false) {
                q.offer(j);
                visit[j] = true;
            }
        }

    }
}