[프로그래머스] 순위 C++

programmers.co.kr/learn/courses/30/lessons/49191

코딩테스트 연습 - 순위

 처음 문제를 보고 단방향 그래프로 문제를 풀어야 하는 줄 알았다. 이긴 사람 기준으로 단방향 그래프를 그려보고, 진 사람 기준으로 단방향 그래프를 그려보고, 방문개수가 적은 순에서 중복이 생기지 않을 때까지 승부가 결정된다고 가정해보고 문제를 풀었다. 아주 멋진 삽질이었다.

 

 정답은 Floyd Warshall 알고리즘을 사용해서 풀어야한다. 2차원 벡터를 사용해 노드 i에서 노드 j까지 가는 최소 거리를 구한다. 그래서 모든 노드 간 최단 이동 거리를 2차원 벡터에 저장하게 된다.

 

그런데 Floyd Warshall 알고리즘을 알았다고 해서 이 문제를 풀 수 있었을까? 노드 i, 노드 j, 노드 k 간 이동거리에서

노드(i-k)의 거리 +  노드(k-j)의 거리 < 노드(i-j)의 거리

 위 조건을 만족할 때 노드(i-j)의 거리는 (i-k) + (k-j)로 업데이트한다는 것이 Floyd Warshall 알고리즘이다. 이 논리를 토대로 "A가 B를 이기고 B가 C를 이기면 A가 C를 이긴 것으로 본다"를 생각하여 도출하는 것이 쉽지 않을 것 같다. 실제 코딩테스트에서 이러한 문제를 마주했을 때, Floyd Warshall을 적용하려면 여러 문제를 접해보아야 할 것 같다.

 마지막 count가 n-1이 되었을때 answer을 증가시키는 이유는, 스스로와 싸울 수 없기 때문이다.

#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <iostream>
using namespace std;

int solution(int n, vector<vector<int>> results) {
    vector<vector<bool>> winner(n,vector<bool>(n,false));
    for(const vector<int>& v:results)
        winner[v[0]-1][v[1]-1] = true;
    
    for(int k=0; k<n; ++k){
        for(int i=0; i<n; ++i){
            for(int j=0; j<n; ++j)
                if( winner[i][k] && winner[k][j] ) winner[i][j] = true;
        }
    }
    
    int answer = 0;
    for(int i=0; i<n; ++i){
        int count = 0;
        for(int j=0; j<n; ++j){
            // i가 j를 이기지 못하고 j가 i를 이기지 못하는 경우 승부는 나지 않는다.
            // 따라서 둘 중 한명이 이기는 경우 승부가 난 것이므로 Count를 증가시킨다.
            // 사실 문제 조건에서 모순은 없다고 하였기 때문에
            // 패배한 경우는 체크하지 않아도 된다
            if(winner[i][j] && !winner[j][i]) count++;
            else if(!winner[i][j] && winner[j][i]) count++;
        }
        if( count == n-1 ) answer++;
    }
    return answer;
}

 도움받은 곳(mungto.tistory.com/58)

순위 C++(그래프)[프로그래머스]

 틀린 풀이. 단방향 그래프로 보고 품.

int solution(int n, vector<vector<int>> results) {
    vector<vector<int>> N_Stack(n,vector<int>());
    for(int i=0; i<results.size(); ++i){
        int win = results[i][0]-1;
        int lose = results[i][1]-1;
        N_Stack.at(lose).push_back(win);
    }

    vector<int> visit_Count(n,0);
    for(int i=0; i<n; ++i){
        queue<int> q;
        q.push(i);
        while(!q.empty()){
            int cur = q.front();    q.pop();
            for(int j:N_Stack.at(cur)){
                visit_Count.at(j)++;
                q.push(j);
            }
        }
    }
    sort(visit_Count.begin(), visit_Count.end());
    int prev = -1;
    int answer = 0;
    
    for(int i:visit_Count){
        if(prev==i){
            answer--;
            break;
        }
        answer++;
        prev = i;
    }
    return answer;
}