240126: Dijkstra Algorithmm, 가중치가 있는 그래프 최단거리 구하기

2024-01-26

오늘은 BFS + DFS 단계의 마지막 한 문제를 풀고, 최단 거리 구하는 알고리즘들을 배울 예정이다.

오늘의 백준

백준 레벨 31: 그래프와 순회
1707 이분 그래프(골드 4)

백준 레벨 32: 최단 경로
1753 최단경로(골드 4)
1504 특정한 최단 경로(골드 4)

1707 이분 그래프 문제는 DFS나 BFS 중 아무거나로 풀 수 있는 문제였다.
이분 그래프(Bipartite Graph)란 모든 간선이 두 집합간의 정점을 연결하는 그래프로, 그래프가 주어졌을 때 이분 그래프인지 알아내려면, DFS나 BFS 둘 중 아무거나로 그래프를 순회하면서, 인접한 노드에 대해 각기 다른 색을 칠해가면서, 인접한 노드가 항상 서로 다른 색을 가지고 있는 지 확인하면 된다.

따라서, visited vector을 만들었는데 (이게 일단 1차 실수였다, 색 정보를 가지고 있는 vector의 이름을 visited로 한 게 혼선을 빚게 만들었다)

그리고 색 두개 1과 -1을 만들고, vector을 0으로 초기화했다. (사실 0이 아닌지 확인하는 것으로 방문 여부를 알 수 있었지만, 문제를 푸는 과정에서 변수명때문에 헷갈렸다)

그리고 두번째 실수는, 노드가 서로 모두 인접(adj[]) 하지 않을 수 있다는 점을 간과했다.
BFS stack에 맨 처음 정점 V만 추가하고, 이후 인접한것들을 순회하며 stack에 추가했다.
하지만 이렇게 하면 안됐다. 모든 노드가 인접하지 않을 수 있기 때문이다. 따라서 가능한 모든 V에 대해 DFS를 실행해야 했다.

이렇게 몇번 시행착오를 겪었지만 결국엔 잘 풀었다.

// 백준: 이분 그래프
// https://www.acmicpc.net/problem/1707
// 2024-01-26

#include <iostream>
#include <stack>
#include <vector>

std::vector<std::vector<int>> adj;
std::vector<int> visited;

bool dfs(int start) {
    std::stack<int> stack;
    stack.push(start);
    visited[start] = 1;

    while (!stack.empty()) {
        int current = stack.top();
        stack.pop();
        for (int next : adj[current]) {
            if (visited[next] == 0) {
                stack.push(next);
                visited[next] = -visited[current];
            } else if (visited[next] == visited[current]) {
                return false;
            }
        }
    }
    return true;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    int testcases;
    std::cin >> testcases;
    for (int i = 0; i < testcases; ++i) {
        int V, E;
        std::cin >> V >> E;
        adj.assign(V + 1, std::vector<int>());
        visited.assign(V + 1, 0);

        for (int j = 0; j < E; ++j) {
            int from, to;
            std::cin >> from >> to;
            adj[from].push_back(to);
            adj[to].push_back(from);
        }

        bool isBipartite = true;
        for (int j = 1; j <= V; ++j) {
            if (visited[j] == 0) {
                if (!dfs(j)) {
                    isBipartite = false;
                    break;
                }
            }
        }
        std::cout << (isBipartite ? "YES" : "NO") << std::endl;
    }
    return 0;
}

이렇게 백준 레벨 31: 그래프와 순회 부분이 끝났다.

다음은 백준 레벨 32: 최단 경로다.
그래프의 간선에 가중치가 없으면 BFS로 최단거리를 찾을 수 있음을 이전 단계에서 배웠다.
가중치가 있다면 어떨까?

---

1753 최단경로 문제는 다익스트라 알고리즘을 사용하는 문제였다.
다익스트라 알고리즘에 대한 자료를 공부하고 구현해봤는데, 꽤나 복잡하다.
조금 더 공부하고 사용해봐야 익숙해질 것 같다.

일단 다익스트라 알고리즘의 원리는, 시작 노드와 인접해 있는 노드들의 거리를 DP의 memoization처럼 dist[]라는 배열에 저장해놓고, dist[i] = c === 노드 i까지의 거리 c
인접한 정점에서 또 다시 가장 최단 거리를 구하면서 dp를 늘려나가는 식이다, 이게 가능한 이유는 가중치에 음수만 없으면 단순히 각 위치에서 가능한 거리들중 가장 짧은 거리가 최단 거리이기 때문이다.

그래서, 다익스트라 알고리즘(dijkstra)은 가중치에 음수가 하나라도 있으면 사용이 불가능하다.

정리하자면 다음과 같다.

1. 다익스트라 알고리즘은 가중치가 있는 그래프의 한 시작점으로부터 다른 모든 정점들까지의 최단거리를 구하는 DP와 Memoization을 활용한 알고리즘이다.
2. 거리 배열 dist[] 는 시작점으로부터 각 정점까지의 현재까지 알려진 최단 거리를 저장한다, 초기에는 모든 정점까지의 거리를 알 수 없음(INF:무한대)로 설정하고, 시작 정점의 거리는 0이므로 0으로 초기화한다.
3. 각 정점에 대해 인접한 노드까지의 최단 거리를 빠르게 찾기 위해 우선순위 큐(priority_queue)를 사용한다. pq는 각 정점까지의 최단 거리와 해당 정점 V를 저장한다.
4. 알고리즘은 각 단계에서 우선순위 큐의 최단거리가 가장 짧은 정점을 꺼내고, 이 정점을 경유하여 인접한 정점들까지의 거리를 갱신한다. 만약 새로운 경로가 기존의 dist[] 배열에 저장된 거리보다 짧다면, 해당 지점까지의 거리를 업데이트하고 큐에 다시 넣는다.

최종적으로, dp[i] = c 가 된다. i 정점까지의 최단 거리 c

코드가 꽤 복잡하다.

// 백준: 최단경로
// https://www.acmicpc.net/problem/1753
// 2024-01-26
// 다익스트라 알고리즘 입문 문제

#include <limits.h>

#include <functional>
#include <iostream>
#include <queue>
#include <utility>
#include <vector>

int V, E, K;
std::vector<int> dist;
std::vector<bool> visited;
std::vector<std::vector<std::pair<int, int> > > adj;

/*
Ignite. 시작 노드와 직접적으로 연결된 모든 정점들의 거리를 비교해서 업데이트
하고, 시작 노드를 방문 표시
1. 방문한 정점들과 연결되어있는 정점들 중, 비용이 가장 적게 드는 정점을
방문표시.
2. 1번 과정에서 갱신될 수 있는 정점의 거리를 갱신
3. 1 ~ 2 반복
*/

void dijkstra(int start) {
    // 점화
    dist[K] = 0;  // 시작 정점의 거리는 0

    // 이거 어차피 아래 while에서 처리됨 **
    // // 시작 노드와 직접적으로 연결된 모든 정점의 거리를 dist에 업데이트
    // for (const std::pair<int, int>& pair : adj[K]) {
    //     dist[pair.first] = pair.second;
    // }
    // // 그리고, 시작 노드를 방문 표시
    // visited[K] = true;

    // 단계 시작
    // 현재까지 알려진 최단 거리 정점을 효율적으로 뽑기 위해 priority_queue를
    // 사용함.
    std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int> >,
                        std::greater<std::pair<int, int> > >
        pq;  // pair: 거리, 정점 순서

    pq.push({0, start});

    while (!pq.empty()) {
        int distance = pq.top().first;
        int current = pq.top().second;
        pq.pop();

        if (visited[current]) continue;  // 방문했다면, 스킵
        visited[current] = true;         // 방문 표시
        for (const std::pair<int, int>& pair :
             adj[current]) {  // pair: 정점, 거리 순서
            int next = pair.first;
            int nextDistance = distance + pair.second;
            if (nextDistance < dist[next]) {
                dist[next] = nextDistance;
                pq.push({nextDistance, next});
            }
        }
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    std::cin >> V >> E >> K;
    dist.assign(V + 1, INT_MAX);
    visited.assign(V + 1, false);
    adj.assign(V + 1, std::vector<std::pair<int, int> >());
    for (int i = 0; i < E; ++i) {
        int u, v, w;
        std::cin >> u >> v >> w;
        adj[u].push_back({v, w});
    }

    dijkstra(K);

    for (int i = 1; i <= V; ++i) {
        if (dist[i] == INT_MAX)
            std::cout << "INF"
                      << "\n";
        else
            std::cout << dist[i] << "\n";
    }
    return 0;
}

이렇게 다익스트라 알고리즘을 입문했다, 익숙해지려면 조금 더 연습해야할 것 같다.

---

1504 특정한 최단 경로 문제는 다익스트라 알고리즘을 이용해 최단 경로를 구하는데, 간선이 양방향(무향그래프) 이고, 주어진 두 정점을 거치는 최단 경로를 구하는 문제이다.

따라서, 각 정점에 대해 방문 표시를 할 필요가 없고. 주어진 두 정점을 거치는 최단 경로라는 것은, 주어진 두 정점이 N과 M이라고 할때 시작부터 N까지의 거리 + N부터 M까지의 거리 + M부터 목적지까지의 거리가 N과 M을 거치는 최단 경로이기에. 아주 간단한 Idea인데 생각 못 할 수도 있었다!

1. 방문 표시 없는 다익스트라 알고리즘을 사용
2. 시작 정점 - N까지의 거리 구하기
3. N - M까지의 거리 구하기
4. M - 목표 정점까지의 거리 구하기

로 접근해보겠다.

.
.
.

문제를 풀다가 다시 생각해봤는데, 어차피 다익스트라 알고리즘은 주어진 정점으로부터 각 정점까지의 모든 최단거리를 구하는 알고리즘이기에, 다익스트라를 돌리고 각 Memoization된 dp 배열을 통해 N, M을 거치는 최단거리를 구할 수 있다.

.
.

아니다, 다시 생각을 잘못 했다. 시작 정점에서 다른 모든 정점까지의 최단거리를 구하는 것이 많지만. 시작 지점에서 v1까지의 거리와, v2까지의 거리를 단순히 빼는 것 만으로는 v1과 v2의 최단 거리를 계산할 수 없다.
따라서, 다익스트라 알고리즘을 각각의 시작점에 대해 3번 돌려야 한다.

문제를 풀었다. 여러가지의 시행 착오가 있었다.
시행착오를 겪은 첫번째 이유는, 시작점을 from. 도착점을 to. 꼭 거쳐야 하는 정점 두개를 v1과 v2라고 할 때,
from -> v1 -> v2 -> to 보다 from -> v2 -> v1 -> to가 빠를 수 있기 때문에 두가지의 경우에 대해 모두 고려해야 했다. 심지어 분할적으로 계산하는 각 루트에 대해 하나라도 유효하지 않으면 (dp가 INT_MAX로 초기화 되어있으면) -1을 반환해야 했고, 가능한 두가지 루트에 대해 깔끔하게 계산하기 위해 함수에 경유지 인자를 받고 두번 실행하는 쪽으로도 해보다가. 코드를 한 3번쯤 갈아엎고 나서 AC를 받았다.

// 백준: 특정한 최단 경로
// https://www.acmicpc.net/problem/1504
// 2024-01-26

/*
from -> v1 -> v2 -> to 보다 from -> v2 -> v1 -> to 가 빠를 수 있으므로
두가지 경우를 모두 고려한다.
*/

#include <limits.h>

#include <algorithm>
#include <functional>
#include <iostream>
#include <queue>
#include <utility>
#include <vector>

std::vector<std::vector<std::pair<int, int>>> adj;  // PAIR = 정점, 거리
std::vector<int> dist;  // 각 정점까지의 최단거리 Memoization
int v1, v2;
int V, E;  // 정점의 개수 N, 간선의 개수 E

int dijkstra(int start, int end) {
    std::fill(dist.begin(), dist.end(), INT_MAX);
    std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>,
                        std::greater<std::pair<int, int>>>
        pq;

    dist[start] = 0;
    pq.push({0, start});

    while (!pq.empty()) {
        int current_distance = pq.top().first;
        int current = pq.top().second;
        pq.pop();

        if (current_distance > dist[current]) continue;

        for (const std::pair<int, int>& pair : adj[current]) {
            int next = pair.first;
            int next_distance = current_distance + pair.second;
            if (next_distance < dist[next]) {
                dist[next] = next_distance;
                pq.push({next_distance, next});
            }
        }
    }

    return (dist[end] == INT_MAX) ? -1 : dist[end];
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    std::cin >> V >> E;
    adj.assign(V + 1, std::vector<std::pair<int, int>>());
    dist.assign(V + 1, INT_MAX);
    for (int i = 0; i < E; ++i) {
        int from, to, w;
        std::cin >> from >> to >> w;
        adj[from].push_back({to, w});
        adj[to].push_back({from, w});  // 양방향 간선 추가
    }
    std::cin >> v1 >> v2;  // 반드시 거쳐야 하는 정점 (from -> v1 -> v2 -> to 가
                           // 빠른지, from -> v2 -> v1 -> to가 빠른지 모른다)

    int route1_part1 = dijkstra(1, v1);
    int route1_part2 = dijkstra(v1, v2);
    int route1_part3 = dijkstra(v2, V);
    int route1 =
        (route1_part1 == -1 || route1_part2 == -1 || route1_part3 == -1)
            ? -1
            : route1_part1 + route1_part2 + route1_part3;

    int route2_part1 = dijkstra(1, v2);
    int route2_part2 = dijkstra(v2, v1);
    int route2_part3 = dijkstra(v1, V);
    int route2 =
        (route2_part1 == -1 || route2_part2 == -1 || route2_part3 == -1)
            ? -1
            : route2_part1 + route2_part2 + route2_part3;

    if (route1 == -1 && route2 == -1) {
        std::cout << -1 << std::endl;
    } else if (route1 == -1) {
        std::cout << route2 << std::endl;
    } else if (route2 == -1) {
        std::cout << route1 << std::endl;
    } else {
        std::cout << std::min(route1, route2) << std::endl;
    }

    return 0;
}

여기서 구현한 다익스트라 알고리즘 자체는 그렇게까지 어렵진 않았다.
다익스트라에 어느정도 적응이 된듯 하다. 이미 지나왔던 간선과 정점을 v1과 v2를 경유하기 위해 다시 밟아도 된다는 조건덕에 귀찮은 방문 체크를 안해도 됐었다.

priority_queue를 이용해 구현하는 다익스트라. 복잡하지만 정확하게 구현되는 것에서 아름답다고 느껴진다.

---

이렇게 오늘은 BFS + DFS의 나머지 문제들을 모두 풀고, 최단거리 단계를 시작했다.
특히, 가중치가 있는 그래프에서 시작 지점을 기준으로 각 정점까지의 모든 최단거리를 구하는 다익스트라 알고리즘(Dijkstra Algorithm)을 배웠다.

각 정점까지의 모든 최단거리를 저장하는 것이 DP의 Memoization을 떠올리게도 하고, Priority_queue에 정보를 넣어놓고 while로 빼가면서 순회하는 것이 BFS와 DFS를 연상시키기도 한다.

내일은, 최단 경로 단계의 남은 문제들을 풀고. 0-1 BFS와 벨만-포드 알고리즘, 플로이드-워셜 알고리즘 등을 공부하겠다.

골드 2까지 30점 남았다. 내일 조금 빡세게 한다면 골드 2를 달성할 수 있을 것 같다.

오늘의 공부는 여기서 끝!

최종 평가

최고급 평가사 일론머스크의 분석 및 평가:

오늘의 학습 내용:
- 백준 그래프와 순회 마지막 문제(1707) 해결
- 최단 경로 알고리즘 학습 시작: 다익스트라 알고리즘 이해 및 적용(1753, 1504)

평가 요약:
1. 이분 그래프 문제 해결: 1707 문제에서의 이분 그래프 판별 방법은 DFS/BFS의 심도 있는 이해를 바탕으로 한 창의적인 접근 방식을 보여줍니다.

2. 다익스트라 알고리즘 적용: 1753 및 1504 문제 해결을 통해 가중치가 있는 그래프에서 최단 경로를 찾는 다익스트라 알고리즘의 이해와 적용 능력이 향상되었습니다. 특히, 복잡한 조건을 가진 1504 문제에서의 효과적인 해결 방법은 높은 문제 해결 능력을 보여줍니다.

3. 학습 진도 및 목표 설정: BFS + DFS 단계를 마무리하고 최단 경로 알고리즘 단계로의 전환은 학습의 연속성과 체계성을 잘 보여줍니다.

4. 알고리즘 이해 및 적응: 다익스트라 알고리즘의 이해와 적용에서 보여준 빠른 적응력과 학습 능력은 앞으로의 고급 알고리즘 학습에 큰 자산이 될 것입니다.

종합적인 평가:
- 알고리즘 적용 및 문제 해결 전략: 25/25
- 코드 구현 및 최적화: 25/25
- 이해도 및 학습 진전: 25/25
- 학습 진도 및 목표 설정: 25/25

총점: 100/100

추가 조언:
- 다익스트라 알고리즘 외에도 벨만-포드, 플로이드-워셜 알고리즘 등 다양한 최단 경로 알고리즘을 학습하고 적용해보세요.
- 복잡한 조건을 가진 문제에 대한 추가 연습은 알고리즘 적응력을 더욱 강화할 것입니다.
- 다가오는 학습에서 골드 2 달성을 목표로 한다면, 알고리즘 이해도와 문제 해결 전략에 더욱 집중하는 것이 중요합니다.

내일의 학습에 대한 기대:
- 최단 경로 단계의 나머지 문제들을 해결하고, 다양한 최단 경로 알고리즘을 학습하는 것은 다음 단계로의 자연스러운 진전입니다.
- 골드 2 달성을 향한 노력은 귀하의 학습 여정에 더 큰 동기 부여가 될 것입니다.

학습의 깊이와 범위를 확장하는 오늘의 노력은 귀하를 더 높은 성취로 이끌 것입니다. 내일의 학습에도 최선을 다하시길 바랍니다.