[BOJ]백준 1865 웜홀 c++ (벨만-포드, Bellman Ford)

 

  문제

---

https://www.acmicpc.net/problem/1865

 

 

  풀이

---

벨만-포드 알고리즘의 경우 주로 그래프 이론에서 음수인 가중치가 있을 때 사용하는 알고리즘입니다. 그래서 문제를 읽자마자 벨만-포드 알고리즘을 써야 된다는 것을 알았습니다. 

사용 배열은 모든 간선을 한 번에 돌기 때문에 1차원 벡터를 선언해주고, 현재까지 값을 저장할 배열을 선언했습니다. 일반 길의 경우엔 방향이 없어 양쪽을 모두 넣어주고, 워프는 단방향이기에 가중치를 음수로하여 저장했습니다. 

vector<pair<pair<int, int>, int>> v;
int dis[501];

...
v.push_back({{s, e}, t});
v.push_back({{e, s}, t});
...

...
v.push_back({{s, e}, -t});
...

 

어떤 간선에서 시작해도 결과가 같기 때문에 1을 고정으로 시작점으로 잡았습니다. 그리고 테스트케이스가 여러 개이기 때문에 함수 선언 시 dis배열을 초기화했습니다. 

 

알고리즘의 틀은 기본 벨만-포드와 같이 n번의 사이클 동안 모든 간선을 돌며 값을 구하고, n+1번째에도 값에 변화가 생기면 이는 무한으로 값이 작아지는 것을 의미하기에 True를 반환하도록 구현했습니다. 

간선을 진행할 때는 간선을 진행하는 게 저장된 값보다 작은 지를 구해서 작은 경우에 갱신하는 방식입니다. 

bool bellman(int n)
{
    memset(dis, 987654321, sizeof(dis));
    dis[1] = 0;

    for (int i = 0; i <= n; i++)
    {
        for (int j = 0; j < v.size(); j++)
        {
            int now = v[j].first.first;
            int next = v[j].first.second;
            int val = v[j].second;

            if (dis[now] != 987654321 && dis[now] + val < dis[next])
            {
                dis[next] = dis[now] + val;
                if (i == n)
                    return 1;
            }
        }
    }
    return 0;
}

 

 

  전체 코드

---

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

vector<pair<pair<int, int>, int>> v;
int dis[501];

bool bellman(int n)
{
    memset(dis, 987654321, sizeof(dis));
    dis[1] = 0;

    for (int i = 0; i <= n; i++)
    {
        for (int j = 0; j < v.size(); j++)
        {
            int now = v[j].first.first;
            int next = v[j].first.second;
            int val = v[j].second;

            if (dis[now] != 987654321 && dis[now] + val < dis[next])
            {
                dis[next] = dis[now] + val;
                if (i == n)
                    return 1;
            }
        }
    }
    return 0;
}

int main()
{
    ios_base ::sync_with_stdio(0);
    cin.tie(0);

    int t;
    cin >> t;

    while (t-- > 0)
    {
        int n, m, w;
        cin >> n >> m >> w;

        for (int i = 0; i < m; i++)
        {
            int s, e, t;
            cin >> s >> e >> t;
            v.push_back({{s, e}, t});
            v.push_back({{e, s}, t});
        }
        for (int i = 0; i < w; i++)
        {
            int s, e, t;
            cin >> s >> e >> t;
            v.push_back({{s, e}, -t});
        }

        cout << (bellman(n) ? "YES\n" : "NO\n");
        v.clear();
    }

    return 0;
}

 

 

  평가

---

 

전형적인 벨만-포드 알고리즘 문제라 연습하기에 좋았습니다.