플로이드 워셜[프로그래머스] 순위

📌 플로이드 워셜

모든 정점에서 모든 정점까지 도달할 수 있는 최솟값을 구하는 알고리즘이다. 방향 그래프, 무방향 그래프 모두에서 적용 가능하다.

🔑 구현방법

노드 -> 노드까지의 거리를 담는 2차원 배열이 있을 때,
1부터 n까지의 노드들을 중간값으로 했을 때의 거리 최솟값을 갱신해주는 방식으로 3중 for문을 사용한다.

즉 1부터한다면
1에서 1까지 1을 거쳐 가는 최솟값,
1에서 2까지 1을 거쳐가는 최솟값,
.
.
.
1에서 1까지 2를 거쳐가는 최솟값,
.
.

이런 식이다.

    // 플로이드 워셜
    for (int i = 1; i <=n ; i++) //중간노드
    {
        for (int j = 1; j <= n; j++) // 시작노드
        {
            for (int k = 1; k <= n; k++) // 도달노드
            {
                dist[j][k] = min(dist[j][k], dist[j][i] + dist[i][k]);
            }
        }
    }

📌 문제 접근

순위 문제는
두 사람 중 누가 앞선 순위인지에 대한 정보가 여러개 주어지면, 순위를 확정할 수 있는 사람이 몇명인지 구하는 문제이다.

처음엔 이문제를 위상정렬로 접근했다.
위상정렬은 문제에 주어진 것처럼 노드들의 순서가 주어질 때, 최종적인 순서를 구현하는 알고리즘으로, 여러가지 답이 나올 수 있다.

그래서 위상정렬을 하는 중간에 순위 선택지가 여러개라면 그 선택지를 안되는 노드로 확정하고, dfs로 모든 경우의 수를 돌리면서 계속 안되는 노드들을 확정하는 식으로 하려고 했는데, 시간초과가 날 것 같았다.

혹은 dfs가 아니라 위상정렬을 하는 중간에 큐에서 노드들을 뺄 때마다 현재 선택지가 여러개인지 1개인지를 업데이트 하면서 여러개라면 안되는 노드로 확정하는 방식으로 하려고 했는데, 어느 노드를 먼저 빼느냐에 따라서 결과값이 달라지는 반례가 있어서 하지 않았다.

📌 올바른 접근

내 순위가 뭔지 안다는 것 = 모든 노드가 나를 이기는지 or 지는지를 아는 것이다.

즉, 방향 그래프에서 a->b로 갈 수 있다는 것은, a 입장에서는 b를 이기는것이고, b 입장에서는 a에게 지는 것이기 때문에 서로 각자의 노드를 이기는지 지는지를 알게 된다.

따라서 플로이드 워셜 알고리즘으로 노드들간의 거리 최솟값을 저장하고, a->b로 가는 거리가 여전히 INF(무한)으로 유지된 경우에는 안된 것으로 판명한다.

📌 풀이 코드

사실 정확한 거리값을 필요로 하는 문제는 아니기 때문에
dist 벡터를 bool로 하고 false를 true로 바꾸는 방식으로 했어도 무방하다.

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

using namespace std;

const int MAX = 101;
int solution(int n, vector<vector<int>> results) {
    int answer = 0;
    vector<vector<int>> dist(n + 1, vector<int>(n+1));
    vector<int> possibCnt(n + 1);

    fill(dist.begin(), dist.end(), vector<int>(n + 1, MAX));
    //fill(&dist[0][0], &dist[n][n], MAX);
    for (int i = 1; i <= n; i++)
    {
        dist[i][i] = 0;
    }

    for (vector<int>& res : results) {
        dist[res[0]][res[1]] = 1;
    }

    // 플로이드 워셜
    for (int i = 1; i <=n ; i++) //중간노드
    {
        for (int j = 1; j <= n; j++) // 시작노드
        {
            for (int k = 1; k <= n; k++) // 도달노드
            {
                dist[j][k] = min(dist[j][k], dist[j][i] + dist[i][k]);
            }
        }
    }

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (dist[i][j]>0 && dist[i][j] < MAX) {
                possibCnt[i]++;
                possibCnt[j]++;
            }
        }
    }

    for (int i = 1; i <= n ; i++)
    {
        if (possibCnt[i] == n - 1) answer++;
    }

    return answer;
}

//int main() {
//
//    cout << solution(5, { {4,3}, {4,2}, {3,2} , {1,2}, {2,5} });
//
//}

플로이드 워셜로 노드간의 거리를 모두 계산하고,
2중 for문을 돌려 a->b 까지 거리가 MAX가 아닌 경우, a,b 모두 확정된 노드 개수를 1씩 더해주었다.

2중for문이 모두 돌고, 자신을 제외한 모든 노드들이 자신보다 앞서있거나 뒷서있는지 아는 노드는 순위가 확정된 것이기 때문에, answer++를 해주었다.