[BOJ알고리즘, C++]#2458, 키 순서, 최단 경로 알고리즘, 플로이드-워셜 알고리즘, 플로이드 알고리즘

 

#1. 문제

2458번: 키 순서

 

---

 

#2. 풀이

 

1. 최단 경로 알고리즘

[알고리즘]#2_길 찾기 알고리즘

 

2. 플로이드(Floyd-Warshall) 알고리즘

 

[정의] : 플로이드 워셜 알고리즘은 최단 경로 알고리즘 중 하나로, 음수 가중치를 포함하는 그래프에서 "전체-쌍" 최단 경로 값을 구하는 알고리즘입니다. 플로이드 알고리즘은 총 3개의 중첩 for 문과 DP의 Memoization을 활용해 그래프 내 모든 쌍의 최단 경로 값을 업데이트합니다.

 

3. 나의 키 순서를 안다는 것은? 나를 기점으로 모든 다른 사람으로 연결되는 경로가 있다!

 

1. 먼저, 플로이드 알고리즘을 통해 전체-쌍에 대한 경로 존재 여부를 확인합니다. 최단 경로 값을 업데이트할 필요는 없다. 단순히, 임의의 출발 정점으로부터 현재 정점까지의 경로가 존재하는지만 확인하면 됩니다! 
2. 그리고, 정점들을 순회하며 다른 모든 정점으로 경로가 존재하는지 확인하고, 그 수가 N-1(모든 정점으로 경로가 존재한다!)이라면, 카운트해줍니다. 즉, 현재 정점은 모든 다른 정점으로 어떻게든 연결되어 있으며, 그로부터 자신의 키 순서를 파악 가능하기 때문입니다.

 

---

 

#3. 코드

 

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

int N, M;
vector<vector<int>> graph;

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

    cin >> N >> M;

    graph.resize(N + 1, vector<int>(N + 1, 0));

    while (M--)
    {
        int a, b;

        cin >> a >> b;

        graph[a][b] = 1;
    }

    for (int k = 1; k <= N; ++k)
    {
        for (int u = 1; u <= N; ++u)
        {
            for (int v = 1; v <= N; ++v)
            {
                if (graph[u][k] != 0 && graph[k][v] != 0 && graph[u][v] == 0)
                {
                    graph[u][v] = 1;
                }
            }
        }
    }

    int res = 0;
    for (int i = 1; i <= N; ++i)
    {
        int cnt = 0;
        for (int j = 1; j <= N; ++j)
        {
            if (i == j)
                continue;

            if (graph[i][j] == 1 || graph[j][i] == 1)
                cnt++;
        }
        if (cnt == N - 1)
            res++;
    }

    cout << res;

    return 0;
}

 

---