[알고리즘 문제 풀기] 웜홀(1865)

1. 문제 풀이 아이디어

• 벨만-포드 알고리즘을 사용해 음수 사이클이 존재하는지 판단하여 문제를 해결할 수 있다.

2. 나의 정답 코드

using System.Text;
StringBuilder sb = new StringBuilder("");

using (StreamReader sr = new StreamReader(Console.OpenStandardInput()))
    using (StreamWriter sw = new StreamWriter(Console.OpenStandardOutput()))
{
    int tc = int.Parse(sr.ReadLine());
    while (tc > 0)
    {
        List<int[]> list = new List<int[]>();
        string[] split = sr.ReadLine().Split();
        int n = int.Parse(split[0]);
        int m = int.Parse(split[1]);
        int w = int.Parse(split[2]);
        for (int i = 0; i < m; i++)
        {
            int[] input = Array.ConvertAll(sr.ReadLine().Split(), int.Parse);
            list.Add(new int[] { input[0], input[1], input[2] });
            list.Add(new int[] { input[1], input[0], input[2] });
        }
        for (int i = 0; i < w; i++)
        {
            int[] input = Array.ConvertAll(sr.ReadLine().Split(), int.Parse);
            list.Add(new int[] { input[0], input[1], -input[2] });
        }
        if (BelmanFord(list, n)) sb.AppendLine("YES");
        else sb.AppendLine("NO");
        tc--;
    }
    sw.WriteLine(sb);
}
bool BelmanFord(List<int[]> list, int n)
{
    int[] dist = new int[n + 1];
    for (int i = 2; i <= n; i++)
    {
        dist[i] = 10000000;
    }

    for (int i = 0; i < n; i++)
    {
        foreach (int[] aa in list)
        {
            int next = dist[aa[0]] + aa[2];
            if (next < dist[aa[1]])
            {
                dist[aa[1]] = next;
                if (i == n - 1)
                    return true;
            }
        }
    }
    return false;
}

3. 정리

• BelmanFord 함수에서 거리 배열을 초기화하고, 정점 수만큼 반복하며 모든 간선을 검사한다.

• 거리 갱신이 마지막 반복(n-1)에서도 발생하면 음수 사이클이 존재하므로 true를 반환한다.

• 이 결과에 따라 테스트케이스마다 "YES" 또는 "NO"를 출력한다.