[항해99 취업 리부트 코스 학습일지] 2024.04.08(월)

오늘은 알고리즘에 기본! 그리고 개인적으로 너무 어려워웠던 깊이 우선 탐색(DFS)와 너비 우선 탐색(BFS)개념을 익히는 시간이였다.

문제를 푸는 것 보다 개념을 이해하는게 더 중요한 날이라 개인적으로 공부를 좀 더 한 날이기도 하다!

 

[01 깊이우선탐색 DFS]

한 방향으로 최대한 깊이 들어가 탐색한 뒤 인접한 다른 정점을 탐색하는 방식입니다.

 

- stack과 재귀를 활용한 방법이 있는데! 정말정말 기초니까! stack을 활용한 방법을 작성해 보겠습니다.

먼저 이런 그림의 그래프가 있다고 하자...

그러면 stack에 쌓여가는 모습을 그려보도록 할 것이다! 

위와 같은 그래프가 있다고 생각해보자

 

그리고 머리속에 stack을 하나 생각해준다. 이제는 넣고 빼고 하는 과정을 그려 볼 것이다.

 

 

코드레벨로 구현하면 다음과 같다.

public class 그래프그리기 {

    private int count;
    private int[][] vertexMatrix;

    public 그래프그리기(int count) {
        this.count = count;
        vertexMatrix = new int[count][count];
    }

    public void addEdge(int from, int to, int weight) {
        vertexMatrix[from][to] = weight;
        vertexMatrix[to][from] = weight;
    }

    public int[][] getVertexMatrix() {
        return vertexMatrix;
    }
}

 

그래프를 그리는 클래스를 만들어줬다. 

import java.util.Stack;

public class DFS검색 {
    int count;
    boolean[] isVisited;
    Stack<Integer> stack;
    int[][] matrix;

    public DFS검색(int count) {
        this.count = count;
        isVisited = new boolean[count];
        stack = new Stack<Integer>();
        // 추가
        matrix = new int[count][count];
    }

    public void DFS경로() {
        stack.push(0);
        isVisited[0] = true;

        while (!stack.isEmpty()) {
            int node = stack.pop();
            System.out.println("지금 출력된 숫자(노드)? " + node);
            // 출력 : 지금 출력된 숫자(노드)?

            for (int i = 0; i < count; i++) {
                if(matrix[node][i] != 0 && !isVisited[i]) {
                    stack.push(i);
                    isVisited[i] = true;
                }
            }
        }
    }

    public static void main(String[] args) {
        int count = 8;
        그래프그리기 graph = new 그래프그리기(count);
        DFS검색 dfs검색 = new DFS검색(count);
        //그래프에 선 추가 (0~1, 길이 1)
        graph.addEdge(0, 1, 1);
        graph.addEdge(0, 2, 1);
        graph.addEdge(1, 3, 1);
        graph.addEdge(1, 4, 1);
        graph.addEdge(2, 5, 1);
        graph.addEdge(2, 6, 1);
        graph.addEdge(4, 5, 1);
        graph.addEdge(3, 7, 1);

        dfs검색.matrix = graph.getVertexMatrix();
        dfs검색.DFS경로();
        // 0,1,3,7,4,5,2,6 or 0,2,6,5,4,1,3,7
    }

}

 

그림과 같이 pop 하는 순간에 노드를 출력하는 코드를 작성했다.

그래서 출력은 ?

 

이렇게 나온다. 

---