[프로그래머스] - 49191_순위

문제 소개

• Level 3 / Graph
• https://school.programmers.co.kr/learn/courses/30/lessons/49191

풀이

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

        // 플로이드 워셜 알고리즘 변형
        for(int[] r:results){
            rank[r[0]][r[1]] = 1; //이김
            rank[r[1]][r[0]] = -1; //짐
        } // 여기까지는 일반 인접행렬과 비슷함

        for(int k=1; k<=n; k++){ // 지금까지의 정보들로 추가적인 승패를 얻을 수 있을지 전체 배열을 확인해보자.
            for(int i=1; i<=n; i++){
                for(int j=1; j<=n; j++){
                    if(rank[i][k]==1 && rank[k][j]==1){ // i번이 k번에게 이긴 정보가 있으며, k번이 j번에게 이긴 정보가 있을 때
                        rank[i][j] = 1; // i번은 j번에게 이긴 것으로 기록하며
                        rank[j][i] = -1; // j번 또한 i번에게 진 것으로 기록한다.
                    }
                }
            }
        }

        for(int i=1; i<=n; i++){ // 이후 승패를 확정지을 수 있는 경우를 찾는다.
            int cnt = 0;
            for(int j=1; j<=n; j++){
                if(rank[i][j]!=0){
                    cnt++;
                }
            }
            if(cnt==n-1){ // 자신을 제외한 모든 이와의 승패가 결정되어 있다면, 등수를 찾을 수 있다.
                answer++;
            }
        }
        return answer;
    }

이번 문제는 플로이드 워셜 알고리즘을 변형하여 이용 해야하는 문제이다.

플로이드 워셜 알고리즘은 모든 최단경로를 구하기 위한 알고리즘으로 각 정점을 중심으로 다른정점 까지의 경로를 찾아낸다.

• 노드 간 최단 거리를 구해야하므로 인접행렬을 구성한다.
  • 노드 간 이어져있지 않다면 거리를 무한으로 설정한다.
  • 노드 간 이어져있다면 거리르 할당한다.
• 중간 노드로 하나의 노드를 선택한 후 이를 통해 최단 거리를 갱신한다.
• 위 방법을 반복하여 각 노드에 대한 최단 경로를 갱신한다.

이러한 플로이드 워셜 알고리즘을 변형해 최단경로를 찾는 대신 각 정점에서 다른 정점으로 갈 수 있는 길을 찾아 기록한다.

• `i`번이 `k`번에게 이긴 정보가 있으며, `k`번이 `j`번에게 이긴 정보가 있을 때
• `i`번은 `j`번에게 이긴 것으로 기록하며, `j`번 또한 `i`번에게 진 것으로 기록한다.

이후 모든 승패가 결정되어있는 경우를 찾아 반환하여 문제를 해결할 수 있다.