알고리즘(C++) / 프로그래머스 level 3 : 순위

level 3 : 순위

https://programmers.co.kr/learn/courses/30/lessons/49191?language=cpp 

코딩테스트 연습 - 순위

 

코드

//프로그래머스 순위
#include <iostream>
#include <string>
#include <vector>

using namespace std;


int solution(int n, vector<vector<int>> results) {
    int answer = 0;

    int graph[101][101] = { false, };

    for (int i = 0; i < results.size(); i++) {
        graph[results[i][0]][results[i][1]] = 1; // graph 생성
    }

    //floyd warshall
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (graph[i][k] && graph[k][j]) {
                    graph[i][j] = 1;
                }
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        int count = 0;
        for (int j = 1; j <= n; j++) {
            if (graph[i][j] || graph[j][i]) { //graph[i][j] : win, graph[j][i] : lose
                count++;
            }
        }
        if (count == n - 1) { //자기 자신을 제외한 모든 사람의 우위를 가릴 수 있음
            answer++;
        }
    }


    return answer;
}

int main() {
    int n = 5;
    vector<vector<int>> results = { {4,3}, {4,2}, {3,2}, {1,2}, {2,5} };
    cout << solution(n, results) << "\n";
    return 0;
}

 

설명

• 이차원 배원 graph를 생성해서 어떤 선수를 이겼는지 배열에 저장한다.
• floyd warshall를 사용하여 모든 선수에 대해 이겼으면 1을 배열에 저장한다.
• floyd warshall은 가중 그래프에서 최단 경로들을 찾는 알고리즘이다. 모든 노드 간의 최단 경로의 길이를 찾을 수 있다. 
• 1번부터 n번까지 우위를 가릴 수 있는 사람이 본인을 제외한 전부라면 정확하게 순위를 매길 수 있다.  

 

고찰

그래프 문제는 쉽게 풀 수 있을 줄 알았지만 그렇지 않았다. 어떻게해야 정확하게 순위를 매길 수 있는 사람의 수를 구할 수 있을지 생각하지 못해서 결국 구글링의 도움으로 문제를 풀 수 있었다. 

floyd 알고리즘은 알고는 있었지만 이런 문제에 적용하려니 막막했다...