[항해99 취업 리부트 코스 학습일지] 2024.04.12.(금)

오늘은 그리디와 다엑스트라알고리즘에 대해 배웠다

사실 BFS 와 다익스트라의 차이점은 아직도 잘 모르겠다.

 

그래서 오늘 배운 것들에 대해 정리해보려고 한다

1. 목적 

- BFS : 시작 정점에서 출발, 그래프를 가까운 정점까지 방문하는 탐색알고리즘, 깊이나 구조 파악하는데 사용

- 다익스트라 : 주어진 출발점에서 최단경로를 찾는 문제

 

2. 가중치 ⭐️

- BFS : 모든 간선의 가중치가 동일

- 다익스트라 : 간선의 가중치가 있는 그래프

 

3. 구현

- BFS : 일반적으로 Queue를 사용

- 다익스트라 : Priority Queue(우선순위 큐 사용), 현재까지 알려진 최단 경로에 따라 정점탐색

 

4. 시간복잡도

V : 정점의 수,  E: 간선의 수

- BFS : 인접리스트 : O( V + E ) 

- 다익스트라 : 우선순위 큐 : O(( V + E ) logV )

 

그래서 정리해본건데, 그래프 구조에 대해 이해하려면 DFS(원하는 요소 있니?) 이런 느낌이고, 다익스트라는 가중치! 가 키워드, 최단경로를찾는 것이 중요하다고 생각합니다유!

---

간단하게 예제로 풀어봅시다 : 결과 해석 있으니까.. 꼭꼭!!! 끝까지 봐야해요

1. 가정

이렇게 생긴 그래프가 있다고 가정해보자.. 노드는 0~5까지의 정수로 이루어져 있고, 각각에 잇지는 노드들 간의 거리를 말한다.

 

2. 거리 배열 최대값으로 채워주기

int[] distances = new int[n]; // n은 노드의 수
Arrays.fill(distances, Integer.MAX_VALUE);

 

3. 시작점 넣어주기 

distances[start] = 0; // 시작점에서의 거리는 0으로 설정합니다.

 

4. 우선순위 큐의 자료형을 클래스 객체로 활용해 그 클래스 안에 있는 객체들을 활용하며 비교합니다.

class Edge implements Comparable<Edge> {
    int target;
    int weight;

    Edge(int target, int weight) {
        this.target = target;
        this.weight = weight;
    }

    @Override
    public int compareTo(Edge other) {
        return Integer.compare(this.weight, other.weight);
    }
}

PriorityQueue<Edge> pq = new PriorityQueue<>();
// 위에 Comparable 구현해도 되고 람다로 비교해도 된다
// PriorityQueue<Edge> pq = new PriorityQueue<>(Comparator.comparingInt(edge -> edge.weight));

 

 

5. 우선순위큐가 비어있지 않을 때의 로직입니다.

 - 우선순위 큐 안에 들어있는 간선의 목적지, 해당 간선의 가중치를 꺼내줍니다

Edge edge = pq.poll(); // 우선순위 큐에서 가장 가중치가 작은 간선을 꺼냄
int node = edge.target; // 해당 간선의 목적지 노드
int dist = edge.weight; // 해당 간선의 가중치

 - 이미 더 짧은 거리로 탐색했다면 -> 넘어가고

 - 현재 노드에서 이동할 수 있는 간선(길이 있는 곳은 탐색한다)

 - 만약 더 짧은 경로를 찾았다면 해당 노드까지 거리를 갱신, 우선순위 큐에 추가한다

for (int i = 0; i < n; i++) { 
        if (graph[node][i] != 0 && distances[i] > distances[node] + graph[node][i]) {
            distances[i] = distances[node] + graph[node][i];
            pq.offer(new Edge(i, distances[i]));
        }
    }

---

전체코드

import java.util.*;

public class DijkstraExample {
    static class Edge {
        int target;
        int weight;

        Edge(int target, int weight) {
            this.target = target;
            this.weight = weight;
        }
    }

    public static void main(String[] args) {
        int[][] graph = {
                {0, 2, 4, 0, 0, 0},
                {0, 0, 1, 7, 0, 0},
                {0, 0, 0, 0, 3, 0},
                {0, 0, 0, 0, 0, 1},
                {0, 0, 0, 2, 0, 5},
                {0, 0, 0, 0, 0, 0}
        };
        int startNode = 0;

        int[] distances = dijkstra(graph, startNode);

        System.out.println("최단 거리:");
        for (int i = 0; i < distances.length; i++) {
            System.out.println("정점 " + i + ": " + distances[i]);
        }
    }

    static int[] dijkstra(int[][] graph, int start) {
        int n = graph.length;
        int[] distances = new int[n];
        Arrays.fill(distances, Integer.MAX_VALUE);
        distances[start] = 0;

        PriorityQueue<Edge> pq = new PriorityQueue<>(Comparator.comparingInt(edge -> edge.weight));
        pq.offer(new Edge(start, 0));

        while (!pq.isEmpty()) {
            Edge edge = pq.poll();
            int node = edge.target;
            int dist = edge.weight;

            if (distances[node] < dist) continue;

            for (int i = 0; i < n; i++) {
                if (graph[node][i] != 0 && distances[i] > distances[node] + graph[node][i]) {
                    distances[i] = distances[node] + graph[node][i];
                    // 큐에 넣기전에 찍어봤다
                    System.out.println("지금 지나간 노드는 ? " + i + "번, 거리(가중치) 는 ? " + distances[i] );

                    pq.offer(new Edge(i, distances[i]));
                }
            }
        }

        return distances;
    }
}

 

출력

 

과정! 

 

[사람이 생각할때]

당연히 최단경로니까 빨간줄 대로 선택해서 2 → 1 → 3 → 2 → 1 순으로 가중치가 더해져 

정점0 : 0

정점1 : 2

정점2 : 3

정점3 : 6

정점4 : 8

정점5 : 9

이렇게 생각했었다..

 

근데 출력값은 왜 

정점3 : 8

정점4 : 6

이 나오는 것일까.... 궁금해졌다.

 

이건 내가 다익스트라 알고리즘을 잘못 이해하고 있었기 때문이였는데.. 

 

알고리즘의 원리를 보면

1. 출발 노드를 설정한다.
2. 최단 거리 테이블을 초기화한다.
3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다.
4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.
5. 3, 4번 과정을 반복한다.

 

큐에 넣기 전 로그를 찍어 본 결과

 

[0번 노드 → 1번 노드]

지금 지나간 노드는 ? 1번, 거리(가중치) 는 ? 2

0번 노드에서 1번 노드로 간 상황, 하나의 케이스 밖에 없다. 

distance[1]  = 2 가 되었다

---

[0번 노드 → 2번 노드]

Comparator.comparingInt(edge -> edge.weight)를 사용하여 간선이 여러개 있을때 처리해주며

지금 지나간 노드는 ? 2번, 거리(가중치) 는 ? 4

0 → 2 (가중치 4)

distance[2]  = 4 가 되었다

지금 지나간 노드는 ? 2번, 거리(가중치) 는 ? 3

0 → 1 → 2 (가중치 0 + 2 + 1 = 3) 

distance[2]  = 3으로 갱신된다

---

[0번 노드 → 3번 노드]
지금 지나간 노드는 ? 3번, 거리(가중치) 는 ? 9

0 → 1 → 3 (가중치 0 + 2 + 7 = 9)

distance[3]  = 9가 되었다

---

[0번 노드 → 4번 노드]

지금 지나간 노드는 ? 4번, 거리(가중치) 는 ? 6

0 → 1 → 2 → 4(가중치 0 + 2 + 1 + 3 = 6)

distance[4]  = 6이 되었다

 

지금 지나간 노드는 ? 3번, 거리(가중치) 는 ? 8

0 → 1 → 2 → 4 까지 왔는데 3번 지나오지 않았는데 갈 수 있네?

0 → 1 → 2 → 4 → 3 마지막에 3번 들려주고 가중치를 계산한다( 0 + 2 + 1 + 3 + 2 = 8)

distance[3]  = 8 로 갱신되었다

---

[0번 노드 → 5번 노드]
지금 지나간 노드는 ? 5번, 거리(가중치) 는 ? 11

지금 위치가 0 → 1 → 2 → 4 까지 와 있는데, 여기서 5번 노드 방문하지 않았으니까  0 → 1 → 2 → 4 → 5

(가중치 : 0 + 2 + 1 + 3 + 5 = 11)

distance[5]  = 11이 되었다.

 

지금 지나간 노드는 ? 5번, 거리(가중치) 는 ? 9

그리고 0 → 1 → 2 → 4 → 3 → 5 로 가는 경우가 또 남았다

(가중치 : 0 + 2 + 1 + 3 + 2 + 1 = 9)

distance[5]  = 9로 업데이트 되어서 

---

최종 업데이트 값 된 distance 배열을 출력하면 ? 

정점0 : 0

정점1 : 2

정점2 : 3

정점3 : 8

정점4 : 6

정점5 : 9

가 출력된다

 

끝입니다