[Algorithm] Programmers :: 순위

https://school.programmers.co.kr/learn/courses/30/lessons/49191

프로그래머스

int graph[101][101] = { false };
 
 
int solution(int n, vector<vector<int>> results) {
    int answer = 0;
 
    for (int i = 0; i < results.size(); ++i)
    {
        graph[results[i][0]][results[i][1]] = true; 
    }
 
    for (int k = 1; k <= n; ++k)
    {
        for (int i = 1; i <= n; ++i)
        {
            for (int j = 1; j <= n; ++j)
            {
                if (graph[i][k] && graph[k][j])
                {
                    graph[i][j] = true;
                }
            }
        }
    }
 
    for (int i = 1; i <= n; ++i)
    {
        int count = 0;
        for (int j = 1; j <= n; ++j)
        {
            if (graph[i][j] || graph[j][i])
            {
                ++count;
            }
        }
 
        if (count == n - 1) ++answer;
    }
 
    return answer;
}

 

먼저 플로이드와샬로 풀이한 문제이다.

승패를 전부 일일이 업데이트한 다음, 특정 선수의 승패결과가 n-1개일 경우(확실한 순위를 알 경우)

++answer하는 풀이이다.

다만 이번문제는 정점이 최대 100이라 괜찮지만 정점이 더 많아질수록 효율은 급감한다.

 

아래 코드는 DFS. 위로 타고가는 그래프와 아래로 타고가는 그래프를 따로 정의해봤다.

vector<vector<int>> upGraph(101);
vector<vector<int>> downGraph(101);
bool visited[101];
 
int upCount = 0;
int downCount = 0;
 
void upDFS(int n)
{
    for (int i = 0; i < upGraph[n].size(); ++i)
    {
        int next = upGraph[n][i];
 
        if (!visited[next])
        {
            ++upCount;
            visited[next] = true;
            upDFS(next);
        }
    }
}
 
void downDFS(int n)
{
    for (int i = 0; i < downGraph[n].size(); ++i)
    {
        int next = downGraph[n][i];
 
        if (!visited[next])
        {
            ++downCount;
            visited[next] = true;
            downDFS(next);
        }
    }
}
 
int solution(int n, vector<vector<int>> results) {
    int answer = 0;
 
    for (int i = 0; i < results.size(); ++i)
    {
        upGraph[results[i][1]].push_back(results[i][0]);
        downGraph[results[i][0]].push_back(results[i][1]);
    }
 
    for (int i = 1; i <= n; ++i)
    {
        upCount = 0;
        downCount = 0;
 
        memset(visited, false, sizeof(visited));
        visited[i] = true;
        upDFS(i);
 
        memset(visited, false, sizeof(visited));
        visited[i] = true;
        downDFS(i);
 
        if (upCount + downCount == n - 1)
        {
            ++answer;
        }
    }
 
    return answer;
}

각 정점에 대해 위로타고 가는 그래프, 즉 자신을 이긴 상대와 그 상대를 이긴 상대를 알수있는 탐색을 정의하고

마찬가지로 아래로 타고 가는 그래프를 정의했다.

위로 올라가면서 카운팅한 값과 아래로 타면서 카운팅한 값을 더했을 때, 이 값이 n-1이면 확실히 승패를 알 수 있기때문에 ++answer을 해준다.

성능은 크게 차이는 없지만 정점개수가 100개가 아니라 그 이상이라면 효율은 더 좋을것이다.