[Progremmers]LV.3 순위

 

📝 풀이 

기본 구조를 가지면 다음과 같다.

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

 

여기서 이제 승패를 1, -1로 표시하면 다음과 같이 나온다.

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

 

문제에서 설명하는 순위를 알 수 있는 것은 자신을 제외한 모든 사람과의 시합을 알 수 있는 사람 즉 모든 배열이 채워진 사람을 말한다. 즉 모든 로직이 끝났을 때 자신을 제외하고 배열에 0이 없는 사람을 검사하면 된다. 

 

[Arogorithm]그래프 - 플로이드워셜

[Arogorithm]그래프 - 플로이드워셜

 

해당 문제처럼 연관 관계를 가진 그래프를 초기화하는 것에 최적화된 것은 플로이드워셜 알고리즘이다. 

 

class Solution {
    public int solution(int n, int[][] results) {
        int[][] map = new int[n + 1][n + 1];
        
        for (int[] result : results) {
            int winner = result[0];
            int loser = result[1];
            map[winner][loser] = 1;
            map[loser][winner] = -1;
        }
        
        // 플로이드-워셜 알고리즘 적용
        for (int k = 1; k <= n; k++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    if (map[i][k] == 1 && map[k][j] == 1) {
                        map[i][j] = 1; 
                    }
                    if (map[i][k] == -1 && map[k][j] == -1) {
                        map[i][j] = -1; 
                    }
                }
            }
        }
        // 자신을 제외하고 0이 아닌 사람을 찾음
        int answer = 0;
        for (int i = 1; i <= n; i++) {
            int count = 0;
            for (int j = 1; j <= n; j++) {
                if (map[i][j] != 0) {
                    count++;
                }
            }
            if (count == n - 1) { 
                answer++;
            }
        }
        
        return answer;
    }
}