[프로그래머스] 순위 (플로이드-워셜 Floyd-warshall)

문제 소개

오늘 풀었던 프로그래머스 - 순위 문제를 정리합니다.

이 문제는 1대1 경기 결과를 통해 선수 간 상대적 순위를 파악할 수 있는지를 묻는 문제입니다.
모든 경기 결과가 주어지는 것이 아니기 때문에, 일부 선수는 순위를 정확히 매길 수 없고, 승패가 명확히 이어지는 선수들만 카운트해야 합니다.

문제 링크: 순위 - 프로그래머스

---

문제 접근 방식

이 문제는 다음과 같은 방식으로 접근했습니다:

1. A가 B를 이김 => A → B 방향의 간선으로 모델링
2. 플로이드-워셜 알고리즘을 사용해, 간접적인 승패 관계까지 모두 파악합니다. (모든 쌍 간 승패 관계 계산)
3. 어떤 선수 i가 모든 다른 선수 j에 대해 (i가 j를 이기거나 j가 i를 이김)이 성립하면 → 순위 확정 가능

---

해결 과정 및 코드

핵심 아이디어

1. chk[i][j] = true → i가 j를 이김
2. chk[i][k] && chk[k][j] → 간접적으로 i가 j를 이김
3. 플로이드-워셜 알고리즘으로 승패 관계를 완성 (모든 쌍 간 승패 관계 계산)
4. 어떤 선수 i에 대해, 자신을 제외한 n-1명과 모두 승/패 관계가 확정돼 있으면 순위도 확정됨

 

코드

시간 복잡도 : O(N^3)

class Solution {
    public int solution(int n, int[][] results) {
        int answer = 0;
        boolean[][] chk = new boolean[n + 1][n + 1]; // 승패 여부를 저장할 배열[][]

        for (int[] r : results) {
            chk[r[0]][r[1]] = true; // r[0]이 r[1]을 이김
        }

		// 플로이드-워셜 알고리즘
        for(int k = 1; k <= n; k++) {
            for(int i = 1; i <= n; i++) {
                for(int j = 1; j <= n; j++) {
                    if(chk[i][k] && chk[k][j]) {
                        chk[i][j] = true;
                    }
                }
            }
        }

		// i번 선수가 다른 모든 선수와 승/패가 정해져 있으면 카운트
        for(int i = 1; i <= n; i++) {
            boolean definite = true;
            for (int j = 1; j <= n; j++) {
                if (i == j) continue;
                // i가 j를 이기지도 않고, j가 i를 이기지도 않으면
		        // => 순위를 확정할 수 없는 선수
                if (!(chk[i][j] || chk[j][i])) {
                    definite = false;
                    break;
                }
            }
            if (definite) answer++;
        }

        return answer;
    }
}