[프로그래머스-49191] 순위

[그래프-순위]

프로그래머스

 

문제

1번 ~ n번까지 n명의 권투선수가 권투 대회 참여함. 권투 경기는 1:1 방식으로 진행,

A 선수 실력 > B 선수 실력 → A 선수는 항상 B 선수 이김

경기 결과 가지고 순위 매기려할 때, 분실된 결과를 바탕으로 정확하게 순위를 매길 수 있는 선수의 수 구하기

제한사항

• 1 ≦ 선수의 수 n ≦ 100
• 1 ≦ 경기 결과 ≦ 4500
• results[A, B] → A 선수가 B 선수 이김
• 모든 경기 결과는 모순 X

입출력 예시

n	results	return
5	[[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]]	2

 

2번 선수는 [1, 3, 4] 선수에게 패배했고, 5번 선수에게 승리했기 때문에 4위

5번 선수는 4위인 2번 선수에게 패배했기 때문에 5위

접근 방법

처음에 플로이드-워셜 알고리즘으로 계산하는 로직을 잘못해서 계속 실패함ㅠㅠ

플로이드-워셜 알고리즘 사용해서 A > B이고 B > C이면 경기 결과 구할 수 있다는 것으로 접근

 

1. 주어진 경기 결과(results)로 이긴 경기는 1로, 진 경기는 -1로 표시
2. DP[i][k] = 1 && DP[k][j] = 1 인 경우에만, DP[i][j] =1, DP[j][i] = -1로 표시
3. 자기자신 제외하고 0의 횟수가 0인 경우에만 정확하게 순위 매길 수 있음

1) 초기 상태

	1	2	3	4	5
1	0	1	0	0	0
2	-1	0	-1	-1	1
3	0	1	0	-1	0
4	0	1	1	0	0
5	0	-1	0	0	0

 

2) k=1

	1	2	3	4	5
1	0	1	0	0	0
2	-1	0	-1	-1	1
3	0	1	0	-1	0
4	0	1	1	0	0
5	0	-1	0	0	0

 

3) k=2

	1	2	3	4	5
1	0	1	0	0	1
2	-1	0	-1	-1	1
3	0	1	0	-1	1
4	0	1	1	0	1
5	-1	-1	-1	-1	0

 

4) k=3, k=4, k=5 동일

5) 최종

	1	2	3	4	5
1	0	1	0	0	1
2	-1	0	-1	-1	1
3	0	1	0	-1	1
4	0	1	1	0	1
5	-1	-1	-1	-1	0

 

6) 0이 아닌 갯수 카운트

	1	2	3	4	5	0의 개수(본인 제외)
1	0	1	0	0	1	2
2	-1	0	-1	-1	1	0
3	0	1	0	-1	1	1
4	0	1	1	0	1	1
5	-1	-1	-1	-1	0	0

 

코드

function solution(n, results) {
    let answer = 0;
    
    const dp = Array.from({length: n+1}, () => Array.from({length: n+1}, () => 0));
    for(const [a, b] of results) {
        dp[a][b] = 1;
        dp[b][a] = -1;
    }
    
    for(let k=1; k<=n; k++) {
        for(let i=1; i<=n; i++) {
            for(let j=1; j<=n; j++) {
                if(dp[i][k] === 1 && dp[k][j] === 1) {
                    dp[i][j] = 1;
                    dp[j][i] = -1;
                }
            }
        }
    }
    
    for(let i=1; i<=n; i++) {
        let cnt = 0; // 0의 개수
        for(let j =1; j<=n; j++) {
            if(i!==j && dp[i][j] === 0) {
                cnt++;
            }
        }
        if(cnt === 0) answer++;
    }
    
    return answer;
}