[프로그래머스 Level_3 / C++ ] 순위

플로이드 와샬 알고리즘을 활용해서 풀어보자. 

해당 알고리즘을 모른다면 맨 아래에 링크에 들어가서 보고 오기를 권한다. 

 

어떤 마을에 A, B, C, D라는 친구들이 있는데, 

가끔 친구들과 누가 더 싸움을 잘하는지 장난 삼아 얘기 해볼 때가 있다.

그러다가 A가 B의 눈빛이 마음에 들지 않아서 싸움을 걸었고 이후 주어진 정보에 따라 1대 1로 맞붙기로 한다. 

 

A는 B와 싸워서 이겼다.

B는 D와 싸워서 이겼다. 

C는 A와 싸워서 이겼다.

 

A :  " D야~ 너는 B와 싸워서 졌으니까 넌 나한테도 져 ㅋㅋㅋㅋ "

 

즉, A는 D와 실제로 싸워본 적이 없지만 이길 수 있다는 것이다. 실제로 컨디션 좋은놈이 이길테지만 문제에선 그렇게 주어지진 않았다. 

 

그렇다면 우리가 세팅해야할 것은 A가 D를 이겼다고 표시를 해줘야 하는 것이다. 

 

그렇다면 여기서 A는 몇등일까? 

 

A는 B한테 이겼고 

A는 D한테 이겼고

 

두번? 아니다 

 

A가 진 것도 체크해야한다. 

 

A는 C한테 졌다. 

 

즉, A는 두번 이겼고 한번 졌다. 

총 4명의 사람이 있고 n-1의 결과를 알 수 있다면 그 친구의 순위를 알 수 있다. 

 

플로이드 와샬을 공부하고 문제를 이해하면 코드 분석하기 어렵지 않을 것이다. 

#include <string>
#include <vector>

using namespace std;

int solution(int n, vector<vector<int>> results) {
    int answer = 0;
    vector<vector<bool>> graph(n+1, vector<bool>(n+1,false)); 
    for(auto x : results) graph[x[0]][x[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 cnt =0; 
        for(int j=1; j<=n; j++){
            if(graph[i][j]||graph[j][i])cnt++; 
        }
        if(cnt==n-1)answer++; 
    }    
    return answer;
}

 

코딩테스트 연습 - 순위

플로이드 와샬 알고리즘