[필수 알고리즘] 폴로이드

개념

- 모든 노드에서 다른 모든 노드까지 가는 최소비용, O(V^3)

- 다익스트라는 한 노드 -> 모든 노드

 

작동원리

- 노드 j -> 노드 i 비용 배열 만들기, 초기값 : INF

- 간선의 값을 비용 배열에 반영

- 모든 노드에 대해 해당 노드 거쳐 비용이 작아질 경우 값 갱신

 

핵심코드

// 플로이드 워셜 알고리즘
for (int k = 1; k <= n; k++) // 거치는 값
{
    for (int j = 1; j <= n; j++) // 시작
    {
        for (int i = 1; i <= n; i++) // 도착
        {
            if (rs[j, k] != INF && rs[k, i] != INF && rs[j, i] > rs[j, k] + rs[k, i])
            {
                rs[j, i] = rs[j, k] + rs[k, i];
            }
        }
    }
}

- 3중 for문 이용

- rs[j, i] 현재 저장 된 값이 rs[j, k] + rs[k, i] 보다 크면 갱신

 

아이디어

- 거리 초기값을 무한대로 설정 후 자기 자신으로 가는 값은 0으로 설정

- 노드를 거쳐 가는 비용이 작아질 경우 값 갱신

 

시간복잡도

- V^3

 

변수

- 거리배열 : int[][]

 

Tip

- 그래프 거리 문제 나올때 사용

-> 한점에서 여러점 : 다익스트라

-> 여러점에서 여러점 : 플로이드

 

 

문제풀이

- 백준11404

 

1.

class num_11404
{
    static void Main(string[] args)
    {
        var sr = new StreamReader(Console.OpenStandardInput());
        var sw = new StreamWriter(Console.OpenStandardOutput());

        int n = Convert.ToInt32(sr.ReadLine());
        int m = Convert.ToInt32(sr.ReadLine());

        //플로이드는 모든 행의 크기가 동일하기 때문에 다차원 배열 사용 
        int[,] rs = new int[n + 1, n + 1];

        
        for (int i = 1; i <= n; i++)
        {
            for (int j = 0; j <= n; j++)
            {
                //자신의 시작점은 0으로 초기화
                if (i == j)
                {
                    rs[i, j] = 0;
                }
                //아니면 전부 최대값 
                else
                {
                    rs[i, j] = int.MaxValue;
                }
            }
        }

        for (int i = 0; i < m; i++)
        {
            string[] input = sr.ReadLine().Split();
            int a = int.Parse(input[0]);
            int b = int.Parse(input[1]);
            int c = int.Parse(input[2]);

            //더 작은 것으로 삽입
            rs[a, b] = Math.Min(rs[a, b], c);
        }
    }
}

- int[,] rs = new int[n + 1, n + 1]; 행의 크기가 같기 때문에 다차원 배열로 선언 후 초기화

- rs[a, b] = Math.Min(rs[a, b], c);로 더 작은 값을 삽입

 

2. 

for (int i = 1; i <= n; i++)//거치는 값
{
    for (int j = 1; j <= n; j++)//시작
    {
        for (int k = 1; k <= n; k++)//도착
        {
            //최대값이 이면 넘기기
            if (rs[j, i] == int.MaxValue || rs[i, k] == int.MaxValue)
            {
                continue;
            }

            //시작 -> 도착 하는 값이 : 시작 -> 거치는 값 + 도착 -> 거치는 값 보다 작으면
            if (rs[j, k] > rs[j, i] + rs[i, k])
            {
                //값 갱신 
                rs[j, k] = rs[j, i] + rs[i, k];
            }
        }
    }
}


for (int i = 1; i <= n; i++)
{
    for (int j = 1; j <= n; j++)
    {
        //최대값이면 0으로 표기해돌라 했기 때문에 0으로 표기
        if (rs[i, j] == int.MaxValue)
        {
            sw.Write("0 ");
        }
        else
        {
            sw.Write($"{rs[i, j]} ");
        }
    }
    sw.WriteLine();
}

sw.Flush();
sw.Close();
sr.Close();

- 거치는 값, 시작, 도착을 이용해  시작 -> 도착 이 시작 -> 거치는 값 + 거치는 값 + 도착 보다 작으면 값 갱신

- 갱신 후 출력

 

최종코드

/*
1. 아이디어
- 모든 점 -> 모든 점 : 플로이드 사용
- 비용 배열 INF 초기화
- 간선 비용 대입
- 거쳐갈때 비용이 작을 경우, 갱신(for문 3번)

2. 시간복잡도
- 플로이드 : O(V^3)

3. 변수
- 비용 배열, int[][]
*/


class num_11404
{
    static void Main(string[] args)
    {
        var sr = new StreamReader(Console.OpenStandardInput());
        var sw = new StreamWriter(Console.OpenStandardOutput());

        int n = Convert.ToInt32(sr.ReadLine());
        int m = Convert.ToInt32(sr.ReadLine());

        //플로이드는 모든 행의 크기가 동일하기 때문에 다차원 배열 사용 
        int[,] rs = new int[n + 1, n + 1];

        
        for (int i = 1; i <= n; i++)
        {
            for (int j = 0; j <= n; j++)
            {
                //자신의 시작점은 0으로 초기화
                if (i == j)
                {
                    rs[i, j] = 0;
                }
                //아니면 전부 최대값 
                else
                {
                    rs[i, j] = int.MaxValue;
                }
            }
        }

        for (int i = 0; i < m; i++)
        {
            string[] input = sr.ReadLine().Split();
            int a = int.Parse(input[0]);
            int b = int.Parse(input[1]);
            int c = int.Parse(input[2]);

            //더 작은 것으로 삽입
            rs[a, b] = Math.Min(rs[a, b], c);
        }

        for (int i = 1; i <= n; i++)//거치는 값
        {
            for (int j = 1; j <= n; j++)//시작
            {
                for (int k = 1; k <= n; k++)//도착
                {
                    //최대값이 이면 넘기기
                    if (rs[j, i] == int.MaxValue || rs[i, k] == int.MaxValue)
                    {
                        continue;
                    }

                    //시작 -> 도착 하는 값이 : 시작 -> 거치는 값 + 도착 -> 거치는 값 보다 작으면
                    if (rs[j, k] > rs[j, i] + rs[i, k])
                    {
                        //값 갱신 
                        rs[j, k] = rs[j, i] + rs[i, k];
                    }
                }
            }
        }


        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                //최대값이면 0으로 표기해돌라 했기 때문에 0으로 표기
                if (rs[i, j] == int.MaxValue)
                {
                    sw.Write("0 ");
                }
                else
                {
                    sw.Write($"{rs[i, j]} ");
                }
            }
            sw.WriteLine();
        }

        sw.Flush();
        sw.Close();
        sr.Close();
    }
}

 

참고영상

- 바로가기