[프로그래머스] 순위 / JAVA

문제 설명 보기

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

코딩테스트 연습 - 순위

> IDEA

A -> B이며 B->C라면, A->C가 성립되는 단방향 그래프에서, 다른 모든 정점과 연결된 정점의 개수를 구하는 문제입니다.

모든 정점에서부터 모든 정점까지 도착하는 경우의 수를 모두 세어야 함으로 플로이드 워셜 알고리즘을 통해 해당 문제가 진짜로 표현하고자 하는 그래프를 그린 다음, 다른 정점과 연결이 안되어있는 정점을 제외하며 답을 세어줍니다.

간선의 가중치가 없으므로 boolean형 인접행렬로 그래프를 표현합니다.

 

> Solution (Floyd-Warchall)

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

        for(int[] intArr : results){
            fw[intArr[0]-1][intArr[1]-1] = true;
        }

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

        int answer = 0;

        for(int i = 0; i < n; i++){
            boolean bl = false;
            for(int j = 0; j < n; j++){
                if(i==j) continue;
                if(fw[i][j] == false && fw[j][i] == false){
                    bl = true;
                    break;
                }
            }
            if(!bl)answer++;
        }

        return answer;
    }
}