[알고리즘 문제 풀기] Road Net(8073)

1. 문제 풀이 아이디어

• i에서 j로 가는 비용이 i → k → j의 비용보다 작거나 같을 때 이웃 도시로 계산하여 문제를 해결할 수 있다.

2. 나의 정답 코드

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

using (StreamReader sr = new StreamReader(Console.OpenStandardInput()))
    using (StreamWriter sw = new StreamWriter(Console.OpenStandardOutput()))
{
    int[] input = Array.ConvertAll(sr.ReadLine().Trim().Split(), int.Parse);
    int n = input[0];
    int[,] map = new int[n + 1, n + 1];
    for (int i = 0; i < n; i++)
    {
        input = Array.ConvertAll(sr.ReadLine().Trim().Split(), int.Parse);
        for (int j = 0; j < n; j++)
        {
            map[i + 1, j + 1] = input[j];
        }
    }
    for (int i = 1; i < n; i++)
    {
        for (int j = i + 1; j <= n; j++)
        {
            bool naver = true;
            for (int k = 1; k <= n; k++)
            {
                if (i == k || j == k || map[i, j] < map[i, k] + map[k, j]) continue;
                naver = false;
                break;
            }
            if (naver) sb.AppendLine($"{i} {j}");
        }
    }
    sw.Write(sb);
}

3. 정리

• 정점 수 n과 인접 행렬을 입력받아 map에 2차원 배열로 저장한다.

• i < j인 모든 정점 쌍에 대해 중간 정점 k를 순회하며 확인한다.

• map[i, j] < map[i, k] + map[k, j]인 경우만 이웃 도시로 판단한다.

• 이웃 도시 그룹은 StringBuilder에 추가하고, 마지막에 한 번에 출력한다.