[프로그래머스 Lv.3] 순위

✨ 정답 ✨

function solution(n, results) {
    const wins = Array.from({ length: n + 1 }, () => new Set());
    const loses = Array.from({ length: n + 1 }, () => new Set());

    for (const [winner, loser] of results) {
        wins[winner].add(loser);
        loses[loser].add(winner);
    }

    for (let i = 1; i <= n; i++) {
        for (let j = 1; j <= n; j++) {
            if (wins[j].has(i)) {
                for (const k of wins[i]) {
                    wins[j].add(k);
                }
            }
            if (loses[j].has(i)) {
                for (const k of loses[i]) {
                    loses[j].add(k);
                }
            }
        }
    }
    let answer = 0;
    for (let i = 1; i <= n; i++) {
        if (wins[i].size + loses[i].size === n - 1) {
            answer++;
        }
    }

    return answer;
}

🧵 참고한 정답지 🧵

💡💡 해설 💡💡

내 코드 설명
그래프에서 모든 정점 쌍 간 최단 경로를 계산하는 데에 사용되는 플로이드-워셜 알고리즘을 사용하는 문제다.
플로이드-워셜 알고리즘 다시 공부해야겠다.