프로그래머스-순위

문제 링크

1. 문제 접근 과정🧐

1. 순위를 정할 수 있으려면 본인이 이길 수 있는 인원 + 지는 인원이 n - 1명이면 된다는 것을 파악
2. 플로이드-워셜 알고리즘으로 i->k가 되고 k->j가 된다면 i->j가 된다는 것을 활용하여 구현
3. 결과를 A가 이기는 B를 win[A][B] = 1로 초기화
4. 플로이드워셜 알고리즘으로 win 배열을 전파
5. i를 보면 win[i][j](이기는 인원) + win[j][i](지는 인원)이 n - 1명이면 순위가 나온다고 체크하여 해결

2. 시행착오🤯

• 그래프를 본인이 이기는 win 그래프와 본인이 지는 lose 그래프 2개로 이기는 인원의 합과 지는 인원의 합이 n - 1인 경우를 보려고 했다.
• 이것이 틀린 풀이는 아니지만 플로이드-워셜 알고리즘으로 푸는 방식이 문제 제한사항으로 통과할 수 있기에 공부하기 위해 이 풀이를 택했다.

3. 개선한 코드😄

• 결과로 win 배열을 초기화하고 플로이드-워셜로 전파하여 결과를 체크하면 된다.
  
• 정답 코드

#include <string>
#include <vector>

using namespace std;

int solution(int n, vector<vector<int>> results) {
    int answer = 0;
    vector<vector<int>> win(n + 1, vector<int>(n + 1, 0));
    for(int i = 0; i < results.size(); i++){
        int A = results[i][0], B = results[i][1];
        win[A][B] = 1;
    }
    for(int k = 1; k <= n; k++){
        for(int i = 1; i <= n; i++){
            if(!win[i][k]) continue;
            for(int j = 1; j <= n; j++){
                if(!win[k][j]) continue;
                win[i][j] = 1;
            }
        }    
    }
    for(int i = 1; i <= n; i++){
        int wins = 0, loses = 0;
        for(int j = 1; j <= n; j++){
            if(i == j) continue;
            if(win[i][j]) wins++;
            if(win[j][i]) loses++;
        }
        if(wins + loses == n - 1) answer++;
    }
    return answer;
}

4. 회고💭

• 플로이드-워셜 알고리즘으로 풀어보니 DFS나 BFS를 하는 것보다 비록 반복문만 활용하면 되므로 구현하는 어려움이 훨씬 적어지는 것 같다.
• 허나 플로이드-워셜은 O(n^3)이므로 제한사항의 n의 크기를 보고 활용할 수 있는지 판단해야 한다.
  • DFS나 BFS를 하면 이 문제는 정방향과 역방향을 해야 하므로 O(n * (n + m))이다.