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

오늘 시험봤는데ㅋㅋㅋㅋ

그 4번 문제 어려웠다 ㅋㅋㅋ 일단 이분탐색 생각하지도 못했고

간선에 무게가 추가되면 어떻게 되는거지 ?.? 물음표만ㅋㅋㅋ 생각하다가 끝났다 ㅋㅋㅋ

지금도 다시 풀다가 머리 식힐 겸 TIL 작성하러 왔다

---

 

[02 너비우선탐색 BFS]

같은 깊이의 가까운 정점들을 차례차례 검사하고 그 다음 깊이로 내려가서 탐색한다.

"최단거리" 를 사용할 때 구현한다고 합니다아아아아! (항상 그런 것은 아니지만, 지금 내 레벨에서는 이렇게 생각하는 것이 정신건강에 이로울 수 있다..) 

 

구현 로직을 살펴보자...

 

이렇게 생긴 그래프가 있다.

일단 너비우선 탐색이기 때문에 하나 선택해서 인접한 노드 모~~두 탐색한다고 생각한다.

 

코드레벨로 구현해 보겠다

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.ArrayList;

public class BFS검색 {
    int count;
    boolean[] isVisited;
    ArrayList<Integer> queue;
    int[][] matrix;

    public BFS검색(int count) {
        this.count = count;
        isVisited = new boolean[count];
        queue = new ArrayList<Integer>();
        matrix = new int[count][count];
    }
    public void BFS경로() {
        queue.add(0);
        isVisited[0] = true;

        while (!queue.isEmpty()) {
            int node = queue.remove(0);
            System.out.println("지금 출력된 숫자(노드)는 ? " + node);

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

    public static void main(String[] args) {
        int count = 8;
        그래프그리기 graph = new 그래프그리기(count);
        BFS검색 bfs검색 = new BFS검색(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);

        bfs검색.matrix = graph.getVertexMatrix();
        bfs검색.BFS경로();
    }
}

 

DFS와는 다르게 arrayList 로 구현되었다.

 

 

출력 결과값이다. 끝!