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

승래·2026년 3월 14일

프로그래머스 Lv.3 - 순위

요구사항

N명의 선수가 있고 경기 결과가 주어질 때
A가 B를 이기면 A는 항상 B를 이김 (실력 순서 일관성 보장)
순위를 정확히 알 수 있는 선수의 수를 구하는 문제

접근 방식

플로이드-워셜 로 모든 선수 간의 승패 관계를 전파했다.

핵심 아이디어

A→B (A가 B를 이김), B→C (B가 C를 이김)
→ A→C (A는 C도 이김) 전파 가능

이유: "A가 B보다 실력이 좋으면 항상 이긴다"는 조건 덕분에
     간접 경로도 항상 성립함

순위 확정 조건

i행 + i열에서 0이 아닌 값의 개수 = n-1
→ 나머지 모든 선수와 승패가 확정됨 = 순위 확정 가능

플로이드-워셜에서 k가 바깥이어야 하는 이유

k가 바깥 = "k를 징검다리로 추가하면서 경로 확장"
→ k=2일 때 2를 거치는 모든 경로 완전히 확정
→ k=3일 때 이미 확정된 정보를 활용해 3을 거치는 경로 확장
→ 순서대로 완전히 확정되면서 전파됨 ✅

k가 안쪽이면 = "아직 확정 안 된 정보를 참조"
→ 놓치는 경로 발생 ❌

코드

import java.util.*;

class Solution {
    public int solution(int n, int[][] results) {
        int answer = 0;
        int[][] arr = new int[n+1][n+1];

        for (int[] result : results) {
            arr[result[0]][result[1]] = 1;
            arr[result[1]][result[0]] = -1;
        }

        // 플로이드-워셜: k가 반드시 바깥 반복문
        for (int k = 1; k <= n; k++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    if (arr[i][k] == 1 && arr[k][j] == 1) {
                        arr[i][j] = 1;
                        arr[j][i] = -1;
                    }
                }
            }
        }

        for (int i = 1; i <= n; i++) {
            int cnt = 0;
            for (int j = 1; j <= n; j++) {
                if (arr[i][j] != 0) cnt++;
            }
            if (cnt == n-1) answer++;
        }

        return answer;
    }
}