99클럽 코테스터디 25일차 TIL 프로그래머스 - 순위

순위

프로그래머스 level 3 그래프

문제링크

문제설명

선수의 수 n, 경기 결과를 담은 2차원 배열 results가 매개변수로 주어질 때
정확하게 순위를 매길 수 있는 선수의 수를 return 하도록 solution 함수를 작성해주세요.

제한사항
-   선수의 수는 1명 이상 100명 이하입니다.
-   경기 결과는 1개 이상 4,500개 이하입니다.
-   results 배열 각 행 \[A, B\]는 A 선수가 B 선수를 이겼다는 의미입니다.
-   모든 경기 결과에는 모순이 없습니다.

 

문제 풀이

선수의 수가 크지 않고 경기의 숫자 또한 크지 않아서 모든 경우의 수를 탐색해 봐도 되겠다고 생각하고 설계 해 봤다.

플로이드 워샬 알고리즘은 모든 노드에서 모든 노드로 까지의 최단거리를 표기할 수 있는 알고리즘 인데, 이를 활용하면 된다.

코드

#include <string>
#include <vector>

using namespace std;

int cal (int arr[102][102], int idx, int n) {
    int res = 0;
    for (int i=1; i<=n; i++) {
        if (arr[i][idx] || arr[idx][i]) res++;
    }

    return res;
}

int solution(int n, vector<vector<int>> results) {
    int answer = 0;
    int arr[102][102];

    for (int i=1; i<=n; i++) {
        fill(arr[i], arr[i]+n+1, 0);
    }

    for (int i=0; i<results.size(); i++) {
        arr[results[i][0]][results[i][1]] = 1;
    }

    for (int k=1; k<=n; k++) {
        for (int i=1; i<=n; i++) {
            for (int j=1; j<=n; j++) {
                if (!arr[i][j] && arr[i][k] && arr[k][j]) {
                    arr[i][j] = 1;
                }
            }
        }
    }

    for (int i=1; i<=n; i++) {
        answer += cal(arr, i, n) == n-1 ? 1 : 0;
    }

    return answer;
}

 

회고

곧 코테를 앞두고 있는데, 플로이드 워샬 같은 알지만 익숙하지 않은 알고리즘을 만나니 반가웠다.

코테 보기전에 다익스트라까지는 해봐야할듯. 플로이드 워샬은 상대적으로 구현이 쉬운데 이 조차도 기억나지 않아서 찾아서 했다.