🌞문제

🌞접근법

n명의 권투선수가 권투 대회에 참여했다. 1~n까지의 번호를 부여받음.
권투는 1대1로 진행한다. A선수가 B선수보다 실력이 좋으면 A선수는 B선수를 이긴다.
심판은 경기결과를 가지고 선수들의 순위를 매긴다.

근데 경기 결과를 몇개 분실했다.

선수의 수 n, 경기 결과를 담은 2차원배열 results 가 주어짐

구해야 하는 값 : 정확하게 순위를 매길 수 있는 선수의 수를 구하여라

조건1. 선수는 1~100명
조건2. 경기 결과는 1개~4500개
조건3. results [A,B] A가 B를 이김

문제를 보고 느낀점은 dfs를 통한 방법이면 해결 할 수 있다고 생각을 했다.
입출력 예제를 살펴보면 results를 탐색을 한다고 할때,
4번을 먼저 탐색을 할 것이다. 그러면 4번은 3번과 2번 선수보다 순위가 높을 것이다.
이에 따라 3번과 2번 선수가 이긴 선수보다도 4번 선수는 순위가 높을 것이다.
따라서
4번 선수는 3번, 2번, 5번 선수보다 순위가 높다. 하지만 1번 선수와는 우열을 가릴 수가 없다.

그렇다면 되는 경우를 살표보자,
2번 선수에 경우에는 4번,3번,1번 선수에게 패하고 5번 선수를 이겼다.
그렇다면 2번 선수는 자신을 제외한 모든 사람을 탐색을 하였으며, 이 때 이긴 선수는 5번 선수뿐이므로 4등이다.

다음은 3번 선수를 살펴보자,
3번 선수는 4번 선수에게 패했다.
그리고 2번 선수를 이겼다. 그렇다는 것은 2번보다는 높지만, 4번보다는 낮은 순위를 가질 것이다.
여기서 2번은 4등이고, 4번은 1등 또는 2등이다. 하지만 1번의 등수는 알지 못하기 때문에 3번은 2등 또는 3등일 것이다.

첫번쨰 풀이방법
1. 두개의 그래프를 만든다. 하나의 노드에 대하여 자신을 이긴 노드의 그래프와 자신한테 진 노드의 그래프 총 두개를 만든다.
2. 하나의 노드에 대하여 이긴 그래프에 대하여 해당 요소들의 이긴 노드는 내가 다 이길 수 있다.
3. 하나의 노드에 대하여 진 그래프에 대해서는 해당 요소들의 진 노드에게는 내가 다 진다.
4. 두개에 대하여 dfs를 돌고 난 이후에 cnt 값을 확인하여 그 값이 n-1이라면 정확하게 순위를 알 수 있는 것이다.

🌞풀이

#include <string>
#include <vector>
#include <iostream>
#include <unordered_map>
#include <memory.h>
#include <set>

using namespace std;

unordered_map<int,vector<int>> win;
unordered_map<int,vector<int>> lose;

int visit[10000];
int result[10000];
set<int> s;

void dfs(int x,unordered_map<int,vector<int>> graph)
{   
    
    for(int i=0;i<graph[x].size();i++)
    {
        int child = graph[x][i];
        if(visit[child]==0)
        {
            visit[child]=1;
            dfs(child,graph);
            s.insert(child);
        }
    }
    
    
}

int solution(int n, vector<vector<int>> results) {
    int answer = 0;

    for(int i=0 ; i < results.size() ; i++)
    {
        int first = results[i][0];
        int second = results[i][1];
        
        if(win.find(first) != win.end())
        {
            win[first].push_back(second);
        }
        else
        {
            vector<int> v;
            v.push_back(second);
            win.insert(make_pair(first,v));
        }
        
        if(lose.find(second) != lose.end())
        {
            lose[second].push_back(first);
        }
        else
        {
            vector<int> v;
            v.push_back(first);
            lose.insert(make_pair(second,v));
        }
    }
    
    for(int i=1;i<n+1;i++)
    {
        
        visit[i] = 1;
        dfs(i,win);
        memset(visit,0,10000);
        
        visit[i] = 1;
        dfs(i,lose);
        memset(visit,0,10000);
        
        
        result[i] = s.size();
        s.clear();
    }
    
    for(int i=1;i<n+1;i++)
    {
        cout << result[i];
        if(result[i] == n-1) answer++;
    }
    
    
    return answer;
}