240128: 플로이드-워셜로 최단 거리 사이클 구하기

2024-01-28

• 1956 운동 풀기 ✅ 2024-01-28
• 다익스트라 복습 ✅ 2024-01-28
• 벨만-포드 복습 ✅ 2024-01-28
• 플로이드-워셜 복습 ✅ 2024-01-28
• 투포인터 시작

오늘은 백준에서 최단 거리 단계의 마지막 부분인: 1956(운동, 골드 4) 문제를 풀었다
이 문제는 V개의 마을과 E의 도로로 구성되는 도시에서, 최단 거리 사이클을 찾는 문제다.
최단 거리 사이클이란 어떠한 경로를 거쳐 자기 자신한테 돌아오는 최단 거리를 말한다. 이 문제의 요구사항은 정확히 당신은 도로를 따라 운동을 하기 위한 경로를 찾으려고 한다. 운동을 한 후에는 다시 시작점으로 돌아오는 것이 좋기 때문에, 우리는 사이클을 찾기를 원한다. 단, 당신은 운동을 매우 귀찮아하므로, 사이클을 이루는 도로의 길이의 합이 최소가 되도록 찾으려고 한다. 다.

처음엔 이 말을 듣고 어떻게 식을 구성해야 할 지 막막했으나, 플로이드-워셜의 기본 개념을 사용하면 됐었다.
음의 사이클 검사 이런건 아니고,, 플로이드-워셜은 각 모든 정점의 쌍에 대해 최단 거리를 구한다.

따라서 2D 배열에 정리되어 있는 dist[]에서 자기 자신이 자기 자신한테 다시 돌아오는 최단 경로(사이클)을 가리키는 것이다 !!

어려워 보이는 문제였는데, 플로이드 워셜 알고리즘의 특성만 잘 알면 꽤 쉽게 풀 수 있는 문제였다.
플로이드 워셜은 다른 최단거리 알고리즘(다익스트라, 벨만-포드)보다 구현이 쉬운 것 같다.

    for (int k = 1; k <= V; ++k) {
        for (int i = 1; i <= V; ++i) {
            for (int j = 1; j <= V; ++j) {
                if (dist[i][k] != LLONG_MAX && dist[k][j] != LLONG_MAX) {
                    if (dist[i][j] > dist[i][k] + dist[k][j])
                        dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }
    ```

하나 중요한 점은 자기 자신으로 돌아오는 사이클을 구하려고 할 때, 원래 하던 것처럼 플로이드-워셜의 dist 배열 자기자신을 0으로 초기화하면 안된다.

사이클을 찾지 않는 상황에서는 자기 자신의 거리를 0으로 초기화하지 않으면, 플로이드-워셜 알고리즘의 결과가 올바르지 않을 수 있다.
왜냐하면 자기 자신으로의 경로는 항상 0이어야 하는데, 이게 0이 아니라 다른 값이면 올바른 최단 경로를 구하지 못하기 때문이다. 처음에 0으로 초기화 하는 건 일종의 기준점과 같다.

하지만, 사이클을 구하려는 상황에서 자기 자신을 0으로 초기화하게 되면, 사이클을 구해봤자 알고리즘은 자기 자신한테 다시 돌아오는 경로의 dist값이 이미 0이 되어있기 때문에, 길이가 0인 사이클을 최단 경로로 잘못 인식할 수 있기 때문이다.

따라서, 사이클을 구하려면 자기 자신을 0으로 초기화 하지 않고. INF 값으로 초기화 한 상태에서 구해서 새로운 값으로 갱신되도록 해야한다. 하지만 이 경우에는 자기 자신의 사이클이 아닌 다른 정점 쌍의 최단 거리가 잘못될 수 있다.

```cpp
long long mincycle = LLONG_MAX;
    for (int i = 1; i <= V; ++i) {
        if (dist[i][i] < mincycle) {
            mincycle = dist[i][i];
        }
    }

    // 사이클 없음
    if (mincycle == 0 || mincycle == LLONG_MAX) {
        std::cout << "-1";
    } else {
        std::cout << mincycle;
    }
    return 0;

---

다익스트라 알고리즘(Dijkstra Algorithm)

Priority Queue를 이용해서(개선 버전, 개선된 다익스트라 알고리즘에서는 최소 힙(min-heap) 구조의 우선순위 큐를 사용하여, 현재까지 발견된 가장 짧은 경로를 가진 노드를 효율적으로 선택한다) 시작 정점을 방문 표시하고(push), 방문 표시된 정점과 인접(adj[])한 정점 중 가장 비용이 적은 곳을 pq에 넣는다.

주의할점은 dist[] 배열을 INF로 초기화해야 한다는 점. pq의 std::pair의 .first에 가중치를 넣어야 pq가 정렬한다는 점에 유의하자. (우선순위 큐에서는 가중치(비용)가 낮은 노드를 우선적으로 처리하기 위해, std::pair의 .first 요소에 가중치를, .second에 노드 번호를 저장한다)

음의 가중치가 없는 그래프에서 가장 효율적으로 시작 정점에서 각 정점까지의 최단 거리를 찾아낼 수 있다.

벨만-포드 알고리즘(Bellman-Ford Algorithm)

벨만-포드 알고리즘은 음의 가중치가 있는 그래프에서 사용할 수 있는 최단 거리 알고리즘으로, 다익스트라 알고리즘 O((V+E)logV) 보다는 비효율적 O(VE) 이다.

V-1 번의 단계를 반복하면서 각 노드간의 최단거리를 구해나가는 방식이다. 다익스트라는 방문하지 않는 노드중에 최단 거리가 가장 가까운 노드만을 방문하는데, 벨만-포드는 매 반복마다 모든 간선을 확인한다.

그래프에서 가능한 모든 경로의 경우의 수는 이론상 V-1번이면 정리된다. 따라서, V-1번 반복하는 과정을 완화(Relaxation) 이라고 한다.

완화 과정이 모두 끝나면 dist 배열은 모두 최단거리만을 가리켜야 한다. 만약 한번 더 완화를 돌렸을 때 최단 거리가 이전보다 더 짧아졌다면, 이는 음의 사이클이 존재하는 것이다. 이 과정을 음의 사이클 검사 라고 한다.

int bellman_ford() {
    dist[1] = 0;
    for (int i = 1; i <= N - 1; ++i) {
        for (int j = 1; j <= N; ++j) {
            for (auto& p : adj[j]) {
                int next = p.second;
                long long weight = p.first;

                if (dist[j] != LLONG_MAX && dist[next] > dist[j] + weight) {
                    dist[next] = dist[j] + weight;
                }
            }
        }
    }

    // 음의 사이클 검사
    for (int j = 1; j <= N; ++j) {
        for (auto& p : adj[j]) {
            int next = p.second;
            long long weight = p.first;
            if (dist[j] != LLONG_MAX && dist[next] > dist[j] + weight) {
                return false;
            }
        }
    }
    return true;
}

플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)

플로이드 워셜 알고리즘은 기본적으로 다이나믹 프로그래밍(Dynamic Programming)에 의거한다.
핵심 아이디어는 거쳐가는 정점을 기준으로 최단거리를 구하는 것이다.

2차원 배열 dist를 선언하고, i와 j를 i -> j 의 비용이라고 설정할 수 있다. dist는 현재까지 알려진 최단거리 테이블이다.

간선이 주어지면 dist에 그대로 초기화하고 알고리즘을 시작한다.

3중 포문으로 거쳐가는 노드, 출발 노드, 도착 노드를 V^3 만큼 돌리며 가능한 모든 경우의 수를 고려하면서 점화식에 맞춰 dist[]를 업데이트 하면 된다. (만약 거쳐서 가는 거리가 지금까지 알려진 최단 거리보다 짧다면 업데이트)

for (int k = 1; k <= n; ++k) {
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (dist[i][k] != LLONG_MAX && dist[k][j] != LLONG_MAX &&
                    dist[i][j] > dist[i][k] + dist[k][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }

플로이드-워셜 알고리즘은 다른 알고리즘과 달리 Idea가 많이 달라서 처음엔 생소할 수 있다.

하지만 플로이드-워셜 알고리즘은 모든 쌍의 노드에 대해 최단 경로를 계산하는 방식이므로, 시간 복잡도는 O(V^3)이지만, 구현이 직관적이고 이해하기 쉽다.

---

내일은 투 포인터 알고리즘에 대해 학습할 예정이다.
말 그대로 두개의 포인터를 이용해 문제를 해결하는 알고리즘이라는데, 내일 목표는 3273, 2470, 1806 세 문제를 푸는 것이다.

최종 평가

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

오늘의 학습 내용:
- 백준 1956 (운동, 골드 4) 문제 해결을 통한 최단 거리 단계 완료
- 다익스트라, 벨만-포드, 플로이드-워셜 알고리즘 복습
- 투 포인터 알고리즘 학습 계획 설정

평가 요약:
1. 최단 거리 알고리즘 적용: 플로이드-워셜 알고리즘을 활용하여 복잡한 사이클 문제를 해결한 점이 뛰어납니다. 다양한 최단 거리 알고리즘에 대한 이해도를 높였습니다.
2. 알고리즘 복습: 다익스트라, 벨만-포드, 플로이드-워셜 알고리즘의 개념을 철저히 복습하고 실제 문제에 적용한 것은 학습의 깊이를 더했습니다.
3. 새로운 알고리즘 도전: 투 포인터 알고리즘에 대한 학습 계획을 세우고 구체적인 문제 해결 목표를 설정한 점은 지속적인 학습 발전을 보여줍니다.

종합적인 평가:
- 기술적 정확성: 30/30
- 알고리즘 적용 및 복습: 25/25
- 새로운 학습 계획 설정: 25/25
- 학습 진도 및 목표 달성: 20/20

총점: 100/100

추가 조언:
- 투 포인터 알고리즘에 대한 학습을 통해 문제 해결 능력을 더욱 확장하세요. 특히, 배열과 리스트에서의 효율적인 탐색 방법을 고려해보세요.
- 최단 거리 알고리즘들에 대한 복습은 계속해서 진행하며, 실제 문제 해결에서 적용해보세요.
- 투 포인터 알고리즘을 활용한 문제들을 통해 새로운 테크닉을 익히고, 이를 다른 알고리즘과의 결합으로 확장해보세요.

오늘의 학습은 최단 경로 알고리즘에 대한 깊은 이해와 새로운 알고리즘 학습으로의 전환을 성공적으로 보여줍니다. 내일의 학습에도 지속적인 성장을 기대합니다.

3줄 요약:
1. 최단 거리 문제 해결 및 최단 거리 알고리즘에 대한 깊은 이해와 복습을 통해 학습의 완성도를 높임.
2. 플로이드-워셜 알고리즘의 특성을 이해하고 이를 통해 복잡한 사이클 문제를 해결.
3. 투 포인터 알고리즘에 대한 학습 계획 설정으로 새로운 알고리즘에 대한 도전을 시작.