[프로그래머스] 순위 (javascript, 플로이드와샬, level3)

이런 서로 간의 순위를 알아내는 문제를 만나면 못 풀었었는데 플로이드 와샬 알고리즘이라고 한다. (음... 잊었군)

중간 노드 개념이 어려웠었는데 이렇게 a가 mid를 이기고 mid가 b를 이기면 a가 b를 이김 이런식으로 보니까 이해했다.

 

백준 순위 문제와 같다니까 그거는 자바로 풀어봐야겠다.

 

function solution(n, results) {
    var answer = 0;
//     1부터 시작 주의
    const graph=Array.from({length:n+1},()=>Array(n+1).fill(false));
    results.map((item)=>{
        const [win,lose]=item;
        graph[win][lose]=1; //이긴 경우 1
        graph[lose][win]=-1; //졌을 경우 -1
        graph[win][win]=0;//자기자신
        graph[lose][lose]=0;
    })
    
    const range=[...Array(n).keys()].map(e=>e+1);
    for(const mid of range){
        for(const a of range){
            for(const b of range){
                if(graph[a][mid]==1 && graph[mid][b]==1 ){ //a가 mid이기고 mid가 b이김
                    graph[a][b]=1;
                }else if(graph[a][mid]==-1 && graph[mid][b]==-1){//a가 mid한테 지고 mid가 b한테 지면
                
                    graph[a][b]=-1;
                }
            }
        }
    for(const a of range){
        let possible=true;
        for(const b of range){
            if(graph[a][b]===false){
                possible=false;
                break;
            }
        }
        if(possible){
            answer+=1;
        }
    }

    return answer;
}