[java] 프로그래머스 (순위) Level 3

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

코딩테스트 연습 - 순위

Approach

플로이드-와샬 알고리즘을 활용하여 풀 수 있는 의외의 문제이다.

기본적인 메커니즘은 이렇다.
result에 {1, 2}, {2, 3}이 있다면, (1, 3)도 결정된다. 경기결과에 없더라도 1과 3사이에 순위를 매길 수 있다.

그런 후, (i, j)와 (j, i)가 모두 갱신이 안되었다면, i 는 순위가 확정되지 않았다고 취급할 수 있다.

1. 먼저 DP배열을 생성한 후, 초기화를 진행한다. (경기결과를 DP배열에 반영)
2. 플로이드-와샬 알고리즘을 수행한 후, i번째 선수가 순위를 확정할 수 있는지를 검사한다.

Code

import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;

import java.util.Arrays;

public class Ranking {
    static final int MAX = 10000;
    public int solution(int n, int[][] result) {
        int[][] dp = new int[n + 1][n + 1];

        // DP 배열 초기화
        for (int[] t : dp) {
            Arrays.fill(t, MAX);
        }
        for (int i = 1; i <= n; i++) {
            dp[i][i] = 0;
        }

        // 경기 결과를 반영(i = win, j = loss)
        for (int[] t : result) {
            dp[t[0]][t[1]] = 1;
        }

        // Floyd-Warshall 알고리즘
        for (int k = 1; k <= n; k++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k][j]);
                }
            }
        }

        // i 의 등수를 확정 지을 수 있는지 판단
        int ans = n;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i == j) {
                    continue;
                }

                if (dp[i][j] == MAX && dp[j][i] == MAX) {
                    ans--;
                    break;
                }
            }
        }
        return ans;
    }

    @Test
    public void test() {
        Assertions.assertEquals(2, solution(5, new int[][]{{4, 3}, {4, 2}, {3, 2}, {1, 2}, {2, 5}}));
    }
}