[알고리즘] 프로그래머스 - 순위

1. 문제

 

2. 나의 풀이

어떻게 풀어야할지 감을 못잡아서 여러 풀이 방법을 찾아 보았는데 플로이드-와샬 알고리즘을 사용해서 푸는 문제 였다.

A가 B를 이기고 B가 C를 이길 경우 A가 C를 이긴다는 형태로 접근을 해야한다.

 

우선 그래프에서 입력으로 온 경기 결과를 입력해준다. 그리고 플로이드-와샬 알고리즘을 이용하여 하나의 노드에서 다른 노드로 갈 수 있는 경로가 있는지 파악한다. 만약 a노드에서 b노드로 갈 수 있다면 a는 b를 이긴 것이다. 역으로 b는 a한테 진 것이다.

 

플로이드-와샬 알고리즘을 수행하고 나면 graph에는 각 선수끼리 싸웠을 때 누가 이기고 졌는지의 결과가 저장되있거나, graph[i][j] = false, graph[j]i[] = false 라면 결과를 알 수 없는 경우 이다.

 

이를 이용하여 순위를 알 수 있는 사람 수를 구한다. 

import java.util.*;

class Solution {

    public int solution(int n, int[][] results) {
        int answer = 0;

        int len = results.length;
        boolean[][] graph = new boolean[n+1][n+1];

        for(int[] p : results){
            graph[p[0]][p[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] == true)
                        graph[i][j] = true;
                }
            }
        }

        //순위를 확실히 알 수 있는 사람 구함
        for(int i=1;i<=n;i++){
            int count = 0;
            for(int j=1;j<=n;j++){  //i ~ j 까지 승패의 or 조건이 true이면 둘이 대결 했을 때 결과를 알 수 있음
                if(graph[i][j] || graph[j][i])
                    count++;
            }

            if(count == n-1)  //자기 자신이랑 싸우는 경우 제외하니까 n-1
                answer++;
        }

        return answer;
    }
}