프로그래머스 순위 JAVA 풀이 (그래프, 플로이드워셜, 순위판별)

🔗 문제 링크

https://programmers.co.kr/learn/courses/30/lessons/49191

---

📌 문제 개요

권투 선수 간 경기 결과가 주어질 때
일부 결과가 누락된 상태에서도 정확한 순위를 알 수 있는 선수 수를 구하는 문제이다.

단, A가 B를 이기면 항상 이긴다는 전제가 존재한다.

---

📌 접근 방법

이 문제는 단순 승패가 아니라
간접 관계까지 포함한 전체 승패 관계를 구해야 한다.

 

따라서 그래프를 사용하여 관계를 저장하고
플로이드-워셜 알고리즘을 통해 모든 경로를 확장한다.

- “직접 승패 + 간접 승패”를 모두 알아야 함,그래서 플로이드-워셜로 모든 승패 관계를 확장하는 것

 

플로이드-워셜 알고리즘
- “모든 정점 쌍 사이의 최단 경로(또는 도달 가능 여부)를 한 번에 구하는 알고리즘”
- 모든 노드 간 관계를 완성시키는 알고리즘

핵심 개념 : 모든 노드 i → j 관계를 구함 중간 노드 k를 거쳐서 더 좋은 경로가 있는지 확인
핵심 로직 : i → j 직접 가는 것보다 i → k → j 가 가능하면 갱신

 

---

📌 핵심 아이디어

• i가 j를 이기거나 j가 i를 이기면 관계가 확정됨
• 모든 선수와의 관계를 알 수 있어야 순위 확정 가능

조건 : 이긴 선수 수 + 진 선수 수 == n - 1

 

이 조건을 만족하면 해당 선수는 순위를 정확히 알 수 있다.

---

📌 처리 흐름

1. graph[i][j] = true (i가 j를 이김)

2. 플로이드-워셜 수행
   i → k && k → j → i → j

3. 각 선수마다
   - win count
   - lose count

4. (win + lose == n - 1) → answer++

---

📌 전체 코드

class Solution {
    public int solution(int n, int[][] results) {
        boolean[][] graph = new boolean[n + 1][n + 1];

        for (int[] r : results) {
            graph[r[0]][r[1]] = true;
        }

        for (int k = 1; k <= n; k++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    if (graph[i][k] && graph[k][j]) {
                        graph[i][j] = true;
                    }
                }
            }
        }

        int answer = 0;

        for (int i = 1; i <= n; i++) {
            int win = 0;
            int lose = 0;

            for (int j = 1; j <= n; j++) {
                if (graph[i][j]) win++;
                if (graph[j][i]) lose++;
            }

            if (win + lose == n - 1) {
                answer++;
            }
        }

        return answer;
    }
}

---

📝 정리

이 문제는 단순 그래프 문제가 아니라

“경로 전파(플로이드 워셜)” + “순위 판별 조건”

 

이 핵심이다. 특히 직접 결과뿐 아니라
간접 승패까지 고려해야 한다는 점이 포인트