[프로그래머스] [C++] 순위 (shortest path)

1. 문제

대결 결과 일부가 주어진다.

 

이 대결 결과는 선수들의 절대적인 실력에 의해 결정된다.

(실력이 더 좋다면 무조건 이김)

 

확실한 순위를 알 수 있는 선수들의 수를 반환하는 프로그램을 작성하여라.

 

 

 

 

2. 최단거리

이 문제는 모든 쌍의 경로를 구하는 문제이다.

 

모든 쌍 알고리즘 중에서 유명한 플로이드 알고리즘이나

 

단일 쌍 알고리즘을 V번 돌리는 알고리즘을 이용하여 문제를 해결 할 수 있다.

 

 

 

 

3. V * dfs

 

이 문제는 가중치가 없으므로 그냥 dfs를 V번 반복하였다.

dfs에서 해당경로를 갈 수 있음을 보여줄 수 있게 src를 함수 매개변수에 추가적으로 넣었다.

 

 

#include <string>
#include <vector>
 
using namespace std;
 
vector<vector<bool> > makeGraph(int n, vector<vector<int> >& results)
{
    vector<vector<bool> > ret(n, vector<bool>(n, 0));
    for(int i = 0; i < n; i++)
        ret[i][i] = true;
    for(int i = 0 ; i < results.size(); i++)
        ret[results[i][0] -1][results[i][1] -1] = true;
    return ret;
}
 
void dfs(int src, int here, vector<bool>& visited ,vector<vector<bool> >& adj)
{
    visited[here] = true;
    for(int there = 0; there < adj[here].size(); there++)
    {
        if(!visited[there] && adj[here][there])
        {
            adj[src][there] = true;
            dfs(src, there, visited, adj);
        }
    }
}
 
void dfsAll(vector<vector<bool> >& adj)
{
    vector<bool> visited;
    for(int i = 0; i < adj.size(); i++)
    {
        visited = vector<bool>(adj.size(), false);
        dfs(i, i, visited, adj);
    }
}
 
int findExactly(vector<vector<bool> >& adj)
{
    int ret = 0;
    for(int i = 0; i < adj.size(); i++)
        for(int j = 0; j < adj[i].size() || (!++ret); j++)
            if(!(adj[i][j]||adj[j][i]))
                break;
    return ret;
}
 
int solution(int n, vector<vector<int>> results) {
    int answer = 0;
    vector<vector<bool> > adj = makeGraph(n, results);
    dfsAll(adj);
    answer = findExactly(adj);
    return answer;
}

 

 

 

 

4. 플로이드 알고리즘

플로이드 알고리즘은 좀 더 구현이 단순하다.

하지만 조금 느린 수행시간을 보여준다.

 

#include <string>
#include <vector>
 
 
using namespace std;
 
vector<vector<bool> > makeGraph(int n, vector<vector<int> >& results)
{
    vector<vector<bool> > ret(n, vector<bool>(n, 0));
    for(int i = 0; i < n; i++)
        ret[i][i] = true;
    for(int i = 0 ; i < results.size(); i++)
        ret[results[i][0] -1][results[i][1] -1] = true;
    return ret;
}
 
void floyd(vector<vector<bool> >& adj)
{
    for(int k = 0; k < adj.size(); k++)
        for(int i = 0; i < adj.size(); i++)
            for(int j = 0; j < adj.size(); j++)
                adj[i][j] = (adj[i][j] || (adj[i][k] && adj[k][j]));
}
 
int findExactly(vector<vector<bool> >& adj)
{
    int ret = 0;
    for(int i = 0; i < adj.size(); i++)
        for(int j = 0; j < adj[i].size() || (!++ret); j++)
            if(!(adj[i][j]||adj[j][i]))
                break;
    return ret;
}
 
 
int solution(int n, vector<vector<int>> results) {
    int answer = 0;
    vector<vector<bool> > adj = makeGraph(n, results);
    floyd(adj);
    answer = findExactly(adj);
    return answer;
}

 

코딩테스트 연습 - 순위 | 프로그래머스 (programmers.co.kr)