문제 링크

프로그래머스 문제

풀이

그래프 문제 입니다.
처음 results간의 관계를 명시한 arr를 생성합니다.
그 후 mid 를 고정한 후, 모든 node에 관한 관계도를 만들어야 합니다.

코드

function solution(n, results) {
    var answer = 0;
    
    let arr = [];
    for(let i=1; i<=n; i++){
        arr[i] = [];
        for(let j=1; j<=n; j++){
            arr[i][j] =false;
        }
    }
    
    for(let i=0; i< results.length; i++){
        const [win, lose] = results[i]
        arr[win][lose] = 1
        arr[lose][win] = -1
        arr[win][win] = 0
        arr[lose][lose] = 0
    }
    
    for(let mid = 1; mid <=n; mid++){ // 왜 mid가 가장 먼저 되어야 할까
        for(let start = 1; start <=n; start++){
            for(let end = 1; end<=n; end++){
                if(arr[start][end] === 1 || arr[start][end] === -1) continue;
                else{
                    if(arr[start][mid] === 1 && arr[mid][end] === 1){
                        arr[start][end] = 1;
                    }
                    if(arr[start][mid] === -1 && arr[mid][end] === -1){
                        arr[start][end] = -1;
                    }
                }
            }   
        }
    }
    
    for(let i =1; i <=n; i++){
           let count = 0;
        for(let j=1; j<=n; j++){
            if(arr[i][j] === 1 || arr[i][j] === -1 ){
                count++;
            }
        }
        if(count === n-1){
            answer++
        }
    }

    
    return answer
}

// 정확하게 순위를 나누는 것이 필요 
// 정확하게 순위를 나눈다는 것은 n명일 때 j의 경기가 최소 n-1개 있어야 한다. 
//