[Programmers] 순위(Lv.3)(C++)

풀이 소요시간 : 40분

정확한 순위를 매길 수 있는 참가자의 숫자를 반환하는 문제다. 각각의 데이터는 승자 와 패자 정보를 가지고, 이를 바탕으로 승자 방향 그래프와 패자 방향 그래프를 구성하였다.

승자 방향 그래프로 탐색 가능한 노드의 수 - 1(본인 노드 제외)
패자 방향 그래프로 탐색 가능한 노드의 수 - 1(본인 노드 제외)

위의 두 값의 합이 n - 1 이 되는 경우 순위를 특정할 수 있다고 판단 가능할 것이다.

방문 체크는 2가지 방식을 사용했다.

현재 노드에서 다음 노드로 가는 경로를 체크하는 Visit 배열
종단 노드의 탐색 완료를 의미하는 Check 배열

그리고 위의 계산식에 사용되는 핵심 값은 Check 배열의 갯수일 것이다.

전체 코드

#include <string>
#include <vector>
#include <cstring>
#include <iostream>
using namespace std;

vector<int> Win[101];
vector<int> Lose[101];

int Visit[101][101];
int Check[101];
int Ans = 0;

//자신 노드 제외
int Check_Count(int n) {
    int cnt = 0;
    for(int i = 1; i <= n; i++)
    {
        if(Check[i] == 1) cnt++;
    }
    return cnt - 1;
}

void Clear() {
    memset(Visit, 0, sizeof(Visit));
    memset(Check, 0, sizeof(Check));
}

void Winner_Count(int n) {
    for(int i = 0; i < Win[n].size(); i++)
    {
        int next = Win[n][i];
        if(Visit[n][next] == 1) continue; 
        
        Visit[n][next] = 1;
        Winner_Count(next);
    }
    
    Check[n] = 1;
}

void Loser_Count(int n) {
    for(int i = 0; i < Lose[n].size(); i++)
    {
        int next = Lose[n][i];
        if(Visit[n][next] == 1) continue;
        
        Visit[n][next] = 1;
        Loser_Count(next);
    }
    
    Check[n] = 1;
}


int solution(int n, vector<vector<int>> results) {

    
    for(vector<int> v : results)
    {
        int win = v[0];
        int lose = v[1];
        
        Win[win].push_back(lose);
        Lose[lose].push_back(win);
    }
    
    for(int i = 1; i <= n; i++)
    {        
        Winner_Count(i);
        int cnt_A = Check_Count(n);
        Clear();
        
        Loser_Count(i);
        int cnt_B = Check_Count(n);
        Clear();
        
        if(cnt_A + cnt_B == n - 1) 
        {
            Ans++;
        }
    }
   
    return Ans;
}