08.07에 푼 문제입니다🌷
순위
다른 분의 풀이를 참고했습니다!
순위 풀이 참고

플로이드 와샬 알고리즘

그래프의 최단 거리를 구하는 알고리즘이다.
그래프에 [i][j] 의 경로를 입력한다.
그리고 중간 다리를 지정해서 [i][k] + [k][j] 값과 비교해서 최단 거리를 입력한다.

Floydwashell(G){
	for i<- 1 to n
    		for j<- 1 to n
            		d[i][j] <- wij
	for k<- 1 to n
    		for i<- 1 to n
    			for j<- 1 to n
                		d[i][j]=min(d[i][j],d[i][k]+d[k]+[j])

시간 복잡도는 O(n^3) 이 된다.

풀이법

플로이드 와샬 알고리즘으로 접근해야 하는 문제이다.
플로이드 와샬 알고리즘은 a->b로 가는 길이 a->mid->b로 가는 길보다
값이 더 클때 a->b로 가는 길의 최단 거리는 a->mid->b가 되는 알고리즘이다.

1. 그래프 만들기

우선 승패를 적은 그래프를 만든다. a가 b를 이겼을 때 graph[a][b] = 1
졌을 경우는 graph[a][b] = -1

2. 플로이드 와샬 알고리즘

mid를 중심으로 [a,b] 를 보고 값이
graph[a][mid]=1 이고 graph[mid][b]=1 일 경우
a->b 이므로 graph[a][b]=1이 된다.

반대로 graph[a][mid]=-1 이고 graph[mid][b]=-1 일 경우
b->a 이므로 graph[a][b]=-1이 된다.

3. 개수세기

순위를 결정 지으려면 한 선수당 n-1개의 승패 여부를 모두 알아야 한다.
승패 여부 중 하나라도 false가 있으면 순위를 알 수 없다.

function solution(n, results) {
    var answer = 0;
    
    const graph = Array.from({ length: n + 1 }, () => Array(n + 1).fill(false));
    results.map(result=>{
        let [win,lose]=result
        graph[win][lose]=1
        graph[lose][win]=-1
        graph[win][win]=0
        graph[lose][lose]=0
    })
    for(let mid = 1; mid<=n;mid++){
        for(let a=1;a<=n;a++){
            for(let b=1;b<=n;b++){
                if(graph[a][mid]===1&&graph[mid][b]===1) graph[a][b]=1
                if(graph[a][mid]===-1&&graph[mid][b]===-1) graph[a][b]=-1
            }
        }
    }
    for(let i=1;i<=n;i++){
        if(graph[i].filter(el=>el===false).length===1) answer++
    }
    return answer;
}