[알고리즘]DFS / BFS

DFS : 깊이 우선 탐색

깊은 부분을 우선적으로 탐색하는 알고리즘

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

최대한 깊이 내려간 뒤, 더이상 깊이 갈 곳이 없을 경우 옆으로 이동

알고리즘 동작방식

스택 자료구조 이용

1. 탐색 시작 노드를 스택에 삽입하고, 방문 처리한다.
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리하고, 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
3. 1과 2를 더이상 수행할 수 없을 때까지 반복한다.

구현 코드(재귀)

import java.util.Deque;
import java.util.LinkedList;

public class dfs2 {
    public static void main(String[] args) {
        int [][]graph = {{},
                {2, 3, 8},
                {1, 7},
                {1, 4, 5},
                {3, 5},
                {3, 4},
                {7},
                {2, 6, 8},
                {1, 7}};

        //각 노드가 방문한 정보를 1차원 배열 자료형으로 표현
        boolean[] visited = {false, false, false, false, false, false, false, false, false};

        //정의된 DFS함수 호출
        dfs2 dfs = new dfs2();
        dfs.dfsTest(graph, 1, visited);
    }

    private void dfsTest(int[][] graph, int start, boolean[] visited) {
        //시작노드 방문처리
        visited[start] = true;
        System.out.print(start + " "); //방문한 노드 출력

        Deque<Integer> stack = new LinkedList<>();

        stack.push(start); //시작 노드 스택에 입력

        while (!stack.isEmpty()) {
            int now = stack.peek();

            boolean hasNearNode = false;//방문하지 않은 인접 노드가 있는지 확인
            //인접 노드를 방문하지 않았을 경우 스택에 넣고 방문처리함
            for(int i : graph[now]){
                if(!visited[i]){
                    hasNearNode = true;
                    stack.push(i);
                    visited[i] = true;
                    System.out.print(i + " ");
                    break;
                }
            }

            if (hasNearNode == false) {
                stack.pop();
            }
        }
    }
}

구현 코드(스택)

import java.util.Deque;
import java.util.LinkedList;

public class dfs2 {
    public static void main(String[] args) {
        int [][]graph = {{},
                {2, 3, 8},
                {1, 7},
                {1, 4, 5},
                {3, 5},
                {3, 4},
                {7},
                {2, 6, 8},
                {1, 7}};

        //각 노드가 방문한 정보를 1차원 배열 자료형으로 표현
        boolean[] visited = {false, false, false, false, false, false, false, false, false};

        //정의된 DFS함수 호출
        dfs2 dfs = new dfs2();
        dfs.dfsTest(graph, 1, visited);
    }

    private void dfsTest(int[][] graph, int start, boolean[] visited) {
        //시작노드 방문처리
        visited[start] = true;
        System.out.print(start + " "); //방문한 노드 출력

        Deque<Integer> stack = new LinkedList<>();

        stack.push(start); //시작 노드 스택에 입력

        while (!stack.isEmpty()) {
            int now = stack.peek();

            boolean hasNearNode = false;//방문하지 않은 인접 노드가 있는지 확인
            //인접 노드를 방문하지 않았을 경우 스택에 넣고 방문처리함
            for(int i : graph[now]){
                if(!visited[i]){
                    hasNearNode = true;
                    stack.push(i);
                    visited[i] = true;
                    System.out.print(i + " ");
                    break;
                }
            }

            if (hasNearNode == false) {
                stack.pop();
            }
        }
    }
}

---

BFS : 너비 우선 탐색

가까운 노드부터 탐색하는 알고리즘

출처 : 출처 https://developer-mac.tistory.com/64
최대한 넓게 이동한 다음, 더 이상 갈 수 없을 때 아래로 이동

알고리즘 동작방식

큐 자료구조 이용
인접한 노드를 반복적으로 큐에 넣도록 알고리즘을 작성

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리한다.
2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리한다.
3. 1, 2 과정을 더이상 수행할 수 없을 때까지 반복한다.

구현 코드

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

public class bfs {
    public static void main(String[] args) {
        //각 노드가 연결된 정보를 2차원 배열로 표현
        int[][]graph = {{},
                {2, 3, 8},
                {1, 7},
                {1, 4, 5},
                {3, 5},
                {3, 4},
                {7},
                {2, 6, 8},
                {1, 7}};

        //각 노드가 방문한 정보를 1차원 배열 자료형으로 표현
        boolean[] visited = {false, false, false, false, false, false, false, false, false};

        int start = 1; //시작노드
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);
        visited[start] = true;
        //큐가 빌때까지 반복
        while (!queue.isEmpty()) {
            //큐에서 하나의 원소를 뽑아서 출력
            int v = queue.poll();
            System.out.print(v + " ");

            //인접 노드 중 아직 방문하지 않은 원소들을 큐에 삽입
            for (int i : graph[v]){
                if(visited[i] == false){
                    queue.add(i);
                    visited[i] = true;
                }
            }
        }
    }
}

문제에 맞는 방법 선택하기

1. 그래프의 모든 정점을 방문하는 것이 중요한 문제 > DFS, BFS 상관없음
2. 경로의 특징을 저장해두어야 하는 문제
   (각 정점에 숫자가 적혀있고 a부터 b까지의 경로를 구하는데 경로에 같은 숫자가 있으면 안된다는 문제 등 각각 경로마다 특징을 저장해두어야 하는 경우) > DFS
3. 최단거리 구하는 문제 > BFS

---

출처
https://devuna.tistory.com/32
https://developer-mac.tistory.com/64
https://velog.io/@smallcherry/Java-AlgorithmBFSAndDFS