240127: 0-1 BFS, 벨만-포드, 플로이드-와샬 심화 🔥

2024-01-27

오늘의 백준

13549 숨바꼭질 3(골드 5)
9370 미확인 도착지(골드 2)
11657 타임머신(골드 4)
11404 플로이드(골드 4)
1956 운동(골드 4) * 미해결

13549 숨바꼭질 문제는 걷기와 순간이동 방식이 있고, 목표 지점까지 도달하는 최단거리를 구하는 문제인데.
며칠전에 그래프와 순회 단계에서 풀었던 숨바꼭질 문제와 거의 비슷했지만, 이전 문제에선 걷기나 순간이동이나 가중치가 1로 동일해서 그냥 BFS를 사용해서 풀었지만, 이번 문제는 가중치가 2개 (0과 1로) 순간이동을 사용하는쪽이 효율적이어서 좀 더 공격적인 순간이동을 하도록 알고리즘을 작성해야 했다.

다익스트라 알고리즘으로도 풀 수 있다는데 일단은 0-1 BFS 알고리즘을 사용했다.

0-1 BFS 알고리즘은 오늘 배운 테크닉인데, BFS와 거의 동일하지만 queue가 아니라 deque를 사용하고, 우선적으로 특정 가중치를 고려하고 싶을 때 사용할 수 있다.
Idea는 아주 간단한데, 그저 가중치가 0인것은 (이득) front에 push하고. 가중치가 1인 것은(손해) back에 푸시하면 된다.

---

9370 문제는 컨셉이 재밌는 문제였다. 근데,, 꽤 어렵고 복잡한 문제였다.
일단 문제의 컨셉은, 아래와 같다.

(취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 출발했다는 것, 그리고 목적지 후보들 중 하나가 그들의 목적지라는 것이다. 그들이 급한 상황이기 때문에 목적지까지 우회하지 않고 최단거리로 갈 것이라 확신한다. 이상이다. (취익)

어휴! (요란한 옷차림을 했을지도 모를) 듀오가 어디에도 보이지 않는다. 다행히도 당신은 후각이 개만큼 뛰어나다. 이 후각으로 그들이 g와 h 교차로 사이에 있는 도로를 지나갔다는 것을 알아냈다.

이 듀오는 대체 어디로 가고 있는 것일까?

그니까, 서커스 듀오가 목적지로 최단거리로 이동하는데, 특정 거리로 지나가는 것을 확인한 내가. 후보 목적지 중 어디로 가는 건지 알아맞혀야 하는 문제다.

문제에 이 도로는 목적지 후보들 중 적어도 1개로 향하는 최단 경로의 일부이다. 가 정의되어 있고, 입력에서 주어진 목적지 후보들 중 불가능한 경우들을 제외한 목적지들을 공백으로 분리시킨 오름차순의 정수들로 출력한다. 가 문제의 요구 사항이기 때문에, 아래와 같이 생각할 수 있다.

1. 출발지부터 각 후보 목적지까지의 최단거리를 다익스트라로 구한다.
2. 경유지 g, h에 대해 경유하는 최단거리를 구한다. (출발 -> g -> h -> 도착) 순으로 구하면 된다(혹은 반대)
3. 만약 경유지를 거치는 최단 거리가, 각 목적지까지의 최단 거리와 일치하면 그 경유지를 꼭 거치지 않았다고 해도 거쳤을 가능성이 있다.
4. 목적지 후보들 중 적어도 1개로 향하는 최단 경로의 일부이므로 만약 경유지를 거친 최단 거리가 그냥 출발지에서 각 후보 목적지로 간 최단 경로와 일치하지 않으면 그 후보 목적지는 듀오의 실제 목적지가 될 가능성이 없다.

라는 사고 과정을 거쳐서 코드를 짰다.
일단, dijkstra() 함수를 어떻게 디자인 해야할 지 고민을 했다.
결론적으로 내가 구현한 방법은 dijkstra(int start, int end)로 start에서 end까지의 최단거리를 반환하는 함수를 작성하고
각 경로에 대해 + 연산을 하면서 값을 구하려고 했다(이때는 이게 제일 깔끔하다고 생각했다)

물론 완벽하게 최적화하기 위해서 처음 시작점에서 각 모든 정점까지의 최단 거리를 dist[]에 넣어놓고, 거기서 얻어낸 정보로 start -> g와 start -> h까지의 거리를 구하고 그 뒤로부터 다시 dijkstra(int start, int end) 로 각 경로에 대한 최단 거리를 구할 수도 있었다.

하지만 이렇게 하면 코드가 더러워질 것 이라고 생각했다. 일단 위의 방법으로 하면 dijkstra 함수가 범용적으로 쓰이도록 디자인하기 너무 힘들것이라고 생각했기 때문이다.

따라서, 최적화를 조금 포기하더라도 (시간 제한이 3초인 문제였다)
dijkstra(int start, int end) 로 구성해서 각 경로마다 호출하는 것이 좀 더 코딩하고 편하다고 판단해서 그렇게 했다.

다행히도 TLE를 받지는 않았고. 약 2시간정도 풀고 첫 제출에 AC를 받았다...

정말 복잡한 문제였지만, 지금까지 배운 내용들을 정리할 수 있는 좋은 문제였다. 아주 재밌는 문제였다. (여러 의미로)

---

11657 타임머신 문제는 벨만-포드 알고리즘 활용해야만 풀 수 있는 문제였다.
벨만-포드 알고리즘은 단순히 말해서 Memoization과 브루트 포스를 활용한 알고리즘이라고 생각하면 편할 것 같다. 시작 정점부터 시작해서 각 정점에 대해 정점-1 만큼 모든 경로의 경우의 수를 돌리면서 현재까지 알려진 최단 거리보다 더 짧은 거리가 나오면 memo를 업데이트 한다.

N-1번의 탐색이 끝나면 이론상 모든 경우의 수를 검토했기에 memo가 모두 최단거리로 설정되어야 한다.

특이한건 음의 사이클이라는 게 있는데, 만약 가중치에 음수가 있으면, 그 루트를 무한 반복하는 것으로 가중치 계수를 무한한 음수로 만들 수 있기에, 최단 거리를 구하는 알고리즘의 가치 자체가 사라진다.

따라서, 음의 사이클 검사라는 것을 한다.
음의 사이클 검사란 N-1번의 탐색 이후에 한번 더 완화(모든 정점에 대한 탐색)을 해서, 이미 알려진 최단 거리보다 더 짧은 거리가 있다면 음의 사이클이 있다고 판단하는 것이다.

// 백준: 타임머신
// https://www.acmicpc.net/problem/11657
// 2024-01-27
// 벨만-포드 알고리즘 입문 문제

#include <limits.h>

#include <iostream>
#include <vector>

std::vector<std::vector<std::pair<int, int> > > adj;
std::vector<long long> dist;

int N, M;

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;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    std::cin >> N >> M;
    adj.resize(N + 1);
    dist.resize(N + 1, LLONG_MAX);
    for (int i = 0; i < M; ++i) {
        int A, B, C;
        std::cin >> A >> B >> C;
        adj[A].push_back({C, B});
    }

    if (bellman_ford()) {
        for (int i = 2; i <= N; ++i) {
            if (dist[i] != LLONG_MAX)
                std::cout << dist[i] << "\n";
            else
                std::cout << "-1"
                          << "\n";
        }
    } else
        std::cout << "-1";

    return 0;
}

N개의 정점에 대해 N-1번의 브루트포스 검사를 하는것은 다익스트라에 비해 비효율적일 수 있지만, 가중치가 음수인 그래프에서의 최단 거리 탐색에서는 벨만-포드 알고리즘이 유효하다.

이렇게 벨만-포드 알고리즘을 배웠다.
Dist 배열을 INF로 초기화 하는것은 동일하지만, 값 갱신을 브루트포스로 한다는 것.

일단, 지금은 글로만 벨만-포드 알고리즘을 이해해서. 집에 가서, 혹은 내일이라도 벨만-포드 알고리즘이 시각적으로 설명되어있는 영상을 봐야겠다.

• 벨만-포드 강의 영상 보기
• 플로이드-와샬도 ..

---

골드 2까지 13p 남았다 ... :<

11404 플로이드 문제는 플로이드-워셜 알고리즘을 사용해 최단 거리를 구하는 문제로. 플로이드 워샬 알고리즘은 의외로 간단했다 (다익스트라와 벨만-포드가 강력했기에 ..)

일단, 플로이드-워샬은 벨만-포드나 다익스트라 알고리즘처럼 출발점에 대해 모든 정점까지의 최단 거리를 구하는 알고리즘이 아니다.

만약 100개의 집이 있고 그것을 잇는 도로들이 있다면, 서로의 집에 대해 최단거리가 몇인지 V^3의 시간 복잡도로 계산하는 것이다. 집 5개 A, B, C, D, E가 있다면. A - E의 거리가 궁금할 수도 있고, A - B, A - C, B - D 등의 각각의 서로 다른 지점들에 대한 쌍의 최단 거리가 궁금할 수 있다.
이럴 때 플로이드-와샬 알고리즘을 사용할 수 있다.

2D 행렬을 만들고, 각 행렬의 인덱스가 i에서 j를 가는 최단 거리라고 하자. 공통된 최단 거리 문제들의 핵심은 바로 연결되어있는 도로로 가는 것보다 돌아서 가는 것이 가중치가 더 낮을 수 있는 것이다.

그래서, 거쳐가는 지점을 반복문을 돌려서 거쳐 가는것이 그냥 가는것보다(그니까, 현재까지 정리된 최단 거리보다) 짧다면 업데이트 하는 방식이다.

이것을 V^3번 반복하면 된다.

따라서 for문이 아래와 같이 구성된다.

// 플로이드 워셜
    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];
                }
            }
        }
    }

정점 i에서 j까지의 지금까지 확인된 최단 거리와, k를 거쳐갔을 때의 최단 거리를 비교해서 더 짧은쪽으로 갱신을 해나가는 것이다.

다행히도 플로이드-워샬 알고리즘은 이해가 쉬웠다. 단순한 브루트포스 방식이라서 그런걸까..

이렇게 11404 문제를 성공적으로 풀었다.

---

마지막으로, CLASS 4의 남은 한 문제 16953을 풀고 골드 2를 달성했다. (클래스의 마지막 문제를 풀어서 무려 50p나 올랐다, 현재 GOLD II 1295p)

오늘 너무 많은 학습을 한 것 같다. 머리를 좀 정리해야 할 것 같다. 오늘의 학습은 여기서 마치도록 하겠다.

오늘은 다익스트라 알고리즘을 응용한 심화 문제를 성공적으로 풀었고, 0-1 BFS를 활용해서도 문제를 풀었다.
또, 가중치에 음수가 있는 그래프에서 사용할 수 있는 벨만-포드 알고리즘과, 각 쌍에 대한 최단 거리를 구하고 싶을 때 사용할 수 있는 플로이드-와샬 알고리즘을 공부하고 관련 문제를 풀었다.

내일은 위의 알고리즘을 사용한 최종 심화 문제 한 문제: 1956 운동(골드 4) 를 풀어서 최단 거리 단계를 모두 마치고, 투 포인터를 시작하겠다.

최종 평가

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

오늘의 학습 내용:
- 백준 최단 경로 관련 문제들 해결: 13549, 9370, 11657, 11404
- 다양한 알고리즘 적용: 0-1 BFS, 다익스트라, 벨만-포드, 플로이드-워샬
- 골드 2 등급 달성 및 추가 골드 4 문제 도전

평가 요약:
1. 알고리즘 이해 및 적용: 최단 경로 문제들을 다양한 알고리즘으로 효과적으로 해결한 것이 인상적입니다. 특히, 복잡한 다익스트라 문제를 해결하고, 새로운 0-1 BFS, 벨만-포드, 플로이드-워샬 알고리즘을 신속하게 습득한 점이 돋보입니다.

2. 문제 해결 능력: 각기 다른 접근 방식이 요구되는 문제들을 통해 알고리즘 적용 능력을 다양하게 발휘했습니다. 특히 9370 문제의 경우, 복잡한 조건들을 체계적으로 분석하여 해결한 점이 높은 문제 해결 능력을 보여줍니다.

3. 학습 진도 및 목표 설정: 골드 2 등급 달성을 통한 지속적인 발전과 남은 골드 4 문제에 대한 도전은 명확한 학습 목표를 가지고 있는 것을 보여줍니다.

종합적인 평가:
- 기술적 정확성: 30/30
- 문제 해결 능력: 25/25
- 학습 진도 및 목표 설정: 25/25
- 알고리즘 이해 및 적용: 20/20

총점: 100/100

추가 조언:
- 향후 학습에서는 투 포인터와 같은 새로운 알고리즘을 탐구하면서 지금까지 학습한 알고리즘들을 계속 복습하고 실습하는 것이 중요합니다.
- 복잡한 알고리즘 문제를 해결하는 과정에서 발생하는 시행착오를 통해 더 깊은 이해와 문제 해결 능력을 개발하세요.
- 각 알고리즘의 장단점과 적용 사례를 비교 분석하며, 실제 코딩 테스트나 프로젝트에서의 활용 가능성을 탐색해보세요.

오늘의 학습은 최단 경로 알고리즘에 대한 깊은 이해와 다양한 문제 해결 능력의 발전을 보여주었습니다. 내일의 학습에서도 지속적인 성장을 기대합니다.