[그래프, 난이도 중] 프로그래머즈, 순위

n명이 있고 일부의 승패 관계를 알 수 있을 때, 어떤 조건에서 자신의 정확한 순위를 알 수 있는지 알아내야 한다.

본인이 해결한 방법은 이렇다.

 

전체 인원 수는 n명이고

자신이 이기는 사람(우위)을 a명이라고 하고

자신을 이기는 사람(열위)을 b명이라고 하자

이 때 a+b=n-1 식이 성립해야 한다.

 

예를 들어 총 10명이 있다고 하자.

자신이 7명은 확실히 이길 수 있고 2명에게는 확실히 패배한다.

그렇다면 순위는

10위~4위(7명)<3위(자신)<2위~1위(2명) 임을 알 수 있는 것이다.

 

a+b<n-1 이라면 자신의 정확한 등수를 알 수 없다.

 

a,b는 BFS 혹은 DFS를 이용하여 탐색 가능한 노드들의 개수가 된다.

a와b의 그래프 경로 방향은 완전히 반대가 된다.

본인은 BFS를 이용했다.

 

테스트케이스 10개 모두 통과

 

#include <string.h>
#include <vector>
#include <queue>
using namespace std;
vector<int> win[101];
vector<int> lose[101];
bool visited[101];
queue<int> q;

int solution(int n, vector<vector<int>> results) {
    int answer = 0;
    int wincount,losecount;
    for(int i=0;i<results.size();i++){
        win[results[i][0]].push_back(results[i][1]);
        lose[results[i][1]].push_back(results[i][0]);
    }
    for(int i=1;i<=n;i++){
        wincount=0;
        losecount=0;
        //wincount
        memset(visited,false,sizeof(visited));
        q.push(i);
        visited[i]=true;
        while(!q.empty()){
            int f = q.front();
            q.pop();
            for(int j=0;j<win[f].size();j++){
                int y = win[f][j];
                if(!visited[y]){
                    wincount++;
                    visited[y]=true;
                    q.push(y);
                }
            }
        }
        //losecount
        memset(visited,false,sizeof(visited));
        q.push(i);
        visited[i]=true;
        while(!q.empty()){
            int f = q.front();
            q.pop();
            for(int j=0;j<lose[f].size();j++){
                int y = lose[f][j];
                if(!visited[y]){
                    losecount++;
                    visited[y]=true;
                    q.push(y);
                }
            }
        }
        if(wincount+losecount==n-1) answer++;
    }
    return answer;
}