[프로그래머스 고득점 kit] 순위 c++ (플로이드 와샬, DFS)

 

문제 링크

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

프로그래머스

 

문제 풀이

문제를 보고 플로이드 와샬이 떠올랐다. 

A >B 이고, B> C 라면   A>C라는 것은 곧,   A 가 1 다리만 걸친다면 B만 이기는 것이지만,  'B' 를 거치면 C 를 이기는 경우의 수를 찾을 수 있기 때문이다.

따라서, i 번 사람이 j 번 사람과 붙어서 이기는가? 에 대해서  아래와 같이 규정하였다.

dp[i][j]
1:  i가 j에게  이긴다
0: i와 j의 승패는 모른다
-1: i가 j에게 진다.

이후,      i -> j 이기는가? 에 대한 탐색을 수행하면서,  k번째 사람을 거치면 어떻게 되는가? 를 체크해나가면, 모든 경우의 수를 찾을 수 있다. 

 

 

정답 코드

#include <string>
#include <vector>

using namespace std;
int dp[101][101];// a가 b를 이겼는가?
vector<int> v[101];
vector<int> loose[101];//내가 진놈
int solution(int n, vector<vector<int>> results) {
    int answer = 0;
     for(int i=0;i<results.size();i++){
        int w=results[i][0],l=results[i][1];
        dp[w][l]=1;
        dp[l][w]=-1;
    }
    for(int k=1;k<=n;k++){ //k를 통한 갱신
        for(int i=1;i<=n;i++){ //i째 사람
                for(int j=1;j<=n;j++){//k의 j에대한 승패
                    if(dp[k][j]==1&&dp[i][k]==1)
                        dp[i][j]=1;// 내가 이긴사람이 이긴사람은 이긴다.
                    if(dp[i][k]==-1&&dp[k][j]==-1)
                        dp[i][j]=-1;// 내가 진 사람이 진 사람은 진다. 
                }
        }
    }
    for(int i=1;i<=n;i++){
        int sum=0;
        for(int j=1;j<=n;j++){
            if(dp[i][j]!=0) sum++;
        }
        if(sum>=n-1)answer++;
    }
    return answer;
}

 

 

+@ DFS 풀이

위의 풀이 외에도, DFS로 푸는 방법역시 구현해보았다. 

어차피 N의 최댓값은 100으로, 시간 복잡도를 고려하지 않아도 되므로 아래와 같이 DFS로 완전 탐색을 돌았다.

 

1. A가 이긴 사람이 이긴 사람을 재귀로 계속해서 찾는다.
2. A가 진 사람이 진사람을 재귀로 계속해서 찾는다.

이를 통해서, 위의 플로이드-와샬 풀이와 동일하게, A>B, B>C then A>C의 규칙을 적용해서 모든 경우의 수를 찾을 수 있다.

정답 코드 2

#include <string>
#include <vector>
#include<unordered_set>
using namespace std;
vector<int> win[101]; //내가 이긴놈
vector<int> loose[101];//내가 진놈
int max_n;
unordered_set<int> as;
void loose_dfs(int n){
    for(int i=0;i<loose[n].size();i++){
        if(as.find(loose[n][i])!=as.end())continue;
        as.insert(loose[n][i]);
        loose_dfs(loose[n][i]);
    }
}

void win_dfs(int n){
   // if(as.size()==max_n-1) return true;
    for(int i=0;i<win[n].size();i++){
        if(as.find(win[n][i])!=as.end())continue;
        as.insert(win[n][i]);
        win_dfs(win[n][i]);
    }    
}


int solution(int n, vector<vector<int>> results) {
    int answer = 0;
    max_n=n;
    for(int i=0;i<results.size();i++){
        int w=results[i][0],l=results[i][1];
        win[w].push_back(l);
        loose[l].push_back(w);
    }
    unordered_set<int> tmp;
    for(int i=1;i<=n;i++){
        int sum=0;
        as=tmp;
        win_dfs(i);
        loose_dfs(i);
        if(as.size()>=n-1)answer++;
    }
    return answer;
}