lv3 순위

변명할 여지가 없다. 그냥 못풀었다.

 

vector<vector<int>> arr = { {1,4}, {2,4}, {3,4}, {4,5}, {4,6}, {5,6} };

첫 생각 :  

노드의 개수가 n개일때 

in 되는 간선과 out 되는 간선이 n-1 개일때 이것을 기준으로 DFS 하는 방식을 취했었다.

 

밑에 코드는 처음 짯을때 기준인데 그냥 그려려니 보자. 틀렸다

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#define pii pair<int, int>
using namespace std;
 
 
vector<int> edge[101];
int in[101] = { 0 };
int out[101] = { 0 };
int check[101] = { 0 };
 
 
void go(int cur_node, int n)
{
    if ( in[cur_node] + out[cur_node] == n-1)
    {
        check[cur_node] = 1;
        for (int i = 0; i < edge[cur_node].size(); i++)
        {
            if (check[edge[cur_node][i]] != 0)
                continue;
            go(edge[cur_node][i], n - in[cur_node]);
        }
    }
 
}
 
 
int solution(int n, vector<vector<int>> arr)
{
 
    for (int i = 0; i < arr.size(); i++)
    {
        out[arr[i][0]]++;
        in[arr[i][1]]++;
 
        edge[arr[i][0]].push_back(arr[i][1]);
    }
 
    for (int i = 1; i <= n; i++)
    {
        cout << in[i] << ' ' << out[i] << '\n';
    }
 
 
    for (int i = 1; i <= n; i++)
    {
        if (check[i] != 0)
            continue;
        if ((in[i] + out[i]) == n - 1)
        {
            check[i] = 1;
 
            for (int j = 0; j < edge[i].size(); j++)
            {
                if (check[edge[i][j]] != 0)
                    continue;
                go(edge[i][j] ,n - in[i]);
            }
        }
    }
 
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        ans += check[i];
    }
    return ans;
}
 
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
 
    int n = 6;
    //vector<vector<int>> arr = { {4,3}, {4,2}, {3,2}, {1,2}, {2,5} };
    vector<vector<int>> arr = { {1,4}, {2,4}, {3,4}, {4,5}, {4,6}, {5,6} };
    cout << solution(n, arr);
 
 
}

 

 

반례는

이렇게 1자류의 그래프는 in+out 이 n-1 인게 없잖음??? 근데 순위를 다 알 수 있다.

 

 

 

정답은

 

 

와셜류를 써보자. 그래프가 100개밖에 안되니 3중포문의 가능성을 생각했어야 됐는데 아깝다..

minnnne.tistory.com/91

여길 참고했다.

 

바로위의 1자형 그래프를 보자.

{{6,5}, {5,4}, {4,3}, {3,2}, {2,1}} 이면

 

map[6][5] = 1; => 6번이 5번에게 이김

map[5][6] = -1; => 6번이 5번에게 짐

을 해주자. 그러면

 

 

이 만들어진다.

그 다음이 개중요하다.

 

2행을 보자. (2번노드)

저길 보면

2번 노드는 3번 노드에게 졌다.

2번 노드는 1번노드에게 이겼다. 라는 것은

3번 노드는 1번노드를 이긴다는 것이다. 이걸 발견하는게 키다.

 

즉 {3,1} 라는 것이 새로 생기고

map[3][1] = 1;

map[1][3] = -1 이라는 것이다.

 

3행을 보자.

3번노드는 1,2번노드에게 이기고 

              4번 노드에게 졌다. 

즉, 

4번 노드는 1,2번 노드를 이긴다는 뜻이다.

4->1, 4->2 라는것이 새로 만들어진다.

 

 

이걸 6행(6번노드)까지 채워 나가면

 

 

이런 웅장한 배열이 만들어진다.

여기서 이걸 갖고 순위를 알수 있는 개수는 각 행마다 -1 or 1의 개수가 n-1 개면 알 수 있으니 적절히 해주면 된다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#define pii pair<int, int>
using namespace std;
 
 
int solution(int n, vector<vector<int>> arr)
{
    int map[101][101] = { 0 };
    
    for (int i = 0; i < arr.size(); i++)
    {
        int in = arr[i][0];
        int out = arr[i][1];
        map[in][out] = 1;
        map[out][in] = -1;
    }
 
 
    for (int i = 1; i <= n; i++)
    {
        vector<int> in; // 상위
        vector<int> out; // 하위
        for (int j = 1; j <= n; j++)
        {
            if (map[i][j] == -1)
                in.push_back(j);
            else if (map[i][j] == 1)
                out.push_back(j);
 
        }
 
        for (int j = 0; j < in.size(); j++)
        {
            for (int k = 0; k < out.size(); k++)
            {
                map[in[j]][out[k]] = 1;
                map[out[k]][in[j]] = -1;
            }
        }
        
    }
 
    int ans = 0;
    for (int i = 1; i <= n ; i++)
    {
        int cnt = 0;
        for (int j = 1; j <= n; j++)
        {
            if (map[i][j] == 1 || map[i][j] == -1)
                cnt++;
        }
        if (cnt == n - 1)
            ans++;
    }
 
 
    return ans;
}