개발공부기록

1. 문제

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

2. 적용할 알고리즘

처음에는 단순히 BFS로 하다가

결국에는 알고리즘 분류를 보고 "벨만포드"를 처음으로 알게 되었다.

벨만포드 알고리즘은 그래프에서 간선의 값이 음수일 때 사용하여

한 노드에서 다른 노드까지의 최소 거리를 알아낼 수 있다.

다익스트라 알고리즘과 비슷하나 그리디한 접근 방식을 사용하지 않고

각각의 반복마다 모든 간선을 확인하여 O(VE)가 되서 다익스트라에 비해

시간이 더 오래 걸린다.

하지만 간선의 값이 음수일 때 사용할 수 있다는게 장점이다.

3. 풀이

이 문제에서 원하는 것은 한 노드에서 출발하여 같은

노드로 시간이 0보다 적게 걸려 도착할 수 있냐는 것이다.

이 말은 그 노드에서 출발하여 되돌아올 수 있는 음수 사이클이 존재하여

그 사이클이 돌 때마다 시간을 줄일 수 있냐는 말이 된다.

위 그림처럼 음수 사이클이 만들어지게 된다면

노드 1에서 다른 노드까지 걸리는 시간은 값이 -4인 간선 때문에

계속해서 작아져 음수가 될 것이고

그 노드까지 걸리는 시간이 음수가 된다면

원래 위치로 돌아 왔을 때 시간이 되돌아간 경우가 된다.

따라서, "음수 사이클이 존재한다면 시간이 되돌아간 경우가 있다"

음수 사이클 존재의 확인을 벨만포드 알고리즘을 통해 알 수 있다.

노드의 개수가 n일 때, n - 1번 동안

각 간선을 거쳐 해당 노드로 가는 비용을 계산하여

최단 거리 테이블을 갱신하고 난 후 한 번 더 계산을 수행한다.

만약 갱신이 또 일어난다면 그것은 음수 사이클이 존재한다는 의미이다.

아무 갱신이 일어나지 않고 최단 거리 테이블이 완성됐다면 음수 사이클이 없다는 의미이다.

4. 코드

#include<iostream>
#include<string>
#include<vector>
#include<queue>
#include<tuple>

using namespace std;

typedef long long ll;

const int INF = 1000'0000;

vector<pair<int, int>> adj[505];

int n, m, w;

int d[505];

bool bf()
{
    fill(d, d + 505, INF);
    
    d[1] = 0;

//n - 1번 동안 모든 간선을 확인해가며 최소 비용을 계산한다.
    for (int i = 0; i < n - 1; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            for (auto nxt : adj[j])
            {
                d[nxt.first] = min(d[nxt.first], d[j] + nxt.second);
            }
        }
    }

//음수 사이클이 존재하는지 확인한다.
    for (int j = 1; j <= n; j++)
    {
        for (auto nxt : adj[j])
        {
            if (d[j] + nxt.second < d[nxt.first]) return true;
        }
    }

    return false;
}

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

    int t;
    cin >> t;

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

        for (int i = 1; i <= n; i++) adj[i].clear();

        for (int i = 0; i < m; i++)
        {
            int s, e, t;
            cin >> s >> e >> t;

            adj[s].push_back({ e, t });
            adj[e].push_back({ s, t });
        }

        for (int i = 0; i < w; i++)
        {
            int s, e, t;
            cin >> s >> e >> t;

            adj[s].push_back({ e, -t });
        }
        cout << (bf() ? "YES" : "NO") << '\n';
    }


}

5. 느낀 점

그래프 문제에서 다익스트라, 벨만포드, 플로이드 알고리즘은

가끔 나오긴 하지만 유용하게 쓰일 때가 있으니 이에 대한

배경지식을 잘 쌓아놓도록 하자...

1. 문제

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

2. 적용할 알고리즘

큐에 명령을 사용한 순서를 string으로 저장하고 bfs를 돌리면 될 것 같다

3. 풀이

큐에서 숫자를 뽑아내 다음 숫자를 선택하는 연산을 그 때 마다 수행하니 시간 초과가 났다.

따라서 res[i][j] 이차원 배열에 숫자 i에서 연산을 하여 나오는 숫자를 j(0, 1, 2, 3)에 미리 저장해놓고

테스트케이스마다 저장해놓은 정보를 가져다 쓰기만 하면 시간을 줄일 수 있다.

시간 제한이 좀 애매하긴 했다. 고작 1/4 줄인다고 해결될 것 같지 않아서 이 방식을 생각하지 않은 것 같다.

테스트 케이스가 여러 개 주어지는 문제에서 미리 필요한 정보를 계산해놓고 정보를 가져다 쓰는 방식을 사용하여 시간을 줄일 수 있다는 걸 기억하자.

4, 코드

#include<iostream>
#include<string>
#include<vector>
#include<queue>
#include<tuple>

using namespace std;

typedef long long ll;

string vis[10005];

int FuncD(int num)
{
    return num * 2 % 10000;
}

int FuncS(int num)
{
    if (num == 0) num = 9999;
    else num--;

    return num;
}

int FuncL(int num)
{
    return (num % 1000) * 10 + num / 1000;
}

int FuncR(int num)
{
    return (num % 10) * 1000 + num / 10;
}

int res[10005][4];

char c[4] = { 'D', 'S', 'L', 'R' };

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

    int t;
    cin >> t;

    for (int i = 0; i <= 9999; i++)
    {
        res[i][0] = FuncD(i);
        res[i][1] = FuncS(i);
        res[i][2] = FuncL(i);
        res[i][3] = FuncR(i);
    }

    while (t--)
    {
        vector<bool> vis(10005);

        int a, b;
        cin >> a >> b;

        string s;

        queue<pair<int, string>> Q;
        Q.push({ a, "" });
        vis[a] = 1;

        while (!Q.empty())
        {
            int cn;
            string cs;
            tie(cn, cs) = Q.front(); Q.pop();

            if (cn == b)
            {
                cout << cs << '\n';
                break;
            }

            for (int i = 0; i < 4; i++)
            {
                int nn = res[cn][i];
                string ns = cs;

                if (vis[nn]) continue;

                ns.push_back(c[i]);
                Q.push({ nn, ns });
                vis[nn] = 1;
                
            }
        }
    }
}