[JAVA] 그래프 "순서"

플로이드 워셜 알고리즘을 이용한다.

 

플로이드 워셜 알고리즘 : skmouse.tistory.com/entry/%ED%94%8C%EB%A1%9C%EC%9D%B4%EB%93%9C-%EC%9B%8C%EC%85%9C-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

플로이드 워셜 알고리즘

for(m=1; m<=N; m++)
    for(s=1; s<=N; s++)
      for(e=1; e<=N; e++)
        if (d[s][e] > d[s][m] + d[m][e])  
        	d[s][e] = d[s][m] + d[m][e];
            
            
    //현재 문제에서 활용한 플로이드 워셜 
for(int i=0; i<n; i++)
	for(int j=0; j<n; j++)
		for(int k=0; k<n; k++)
			if(game[j][i]&&game[i][k])
            			game[j][k]=true;
                

---

위의 플로이드 워셜을 이용하여,

j->i 가 뚫려있고 i->k가 뚫려있으면 j->k를 뚫어놓는 방식이다.

 

기존의 min메소드를 이용하여 비교하는것과는 다른 차이점이 있지만, 같은 개념이다.

 

 

 

 

순위를 확정짓는 조건 :

경기 결과의 중복없이 n-1 회의 경기 결과를 도출 하는가?

class Solution {
    public int solution (int n, int[][] results){
        boolean[][] game =  new boolean[n][n];
        int answer = 0;
        for(int i=0; i<results.length; i++){ game[results[i][0]-1][results[i][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(game[j][i]&&game[i][k]){game[j][k]=true;}
                }
            }
        }
	
    
    //a선수가 b선수에게 승리했거나, 패배했다면 경기결과를 +1 합니다.
	//(arr[a][b] 혹은 arr[b][a] 가 true라면)
      for(int i=0; i<n; i++){
            int result=0;
            for(int j=0; j<n; j++){
                if(game[i][j] || game[j][i]){result++;}
            }
            if(result==n-1){answer++;}
        }
        return answer;
    }
}

입출력 예

 

입출력 예시에 따르면

1번선수는 2,5번 선수에게 승리

2번선수는 1,3,5번 선수에게 패배, 5번선수에게 승리 => n-1 =4 성립

3번선수는 2,5번 선수에게 승리, 4번선수에게 패배

4번선수는 2,3,5번 선수에게 승리

5번선수는 1,2,3,4번 선수에게 패배 => n-1 = 4 성립

 

따라서 2,5번 선수만 등수를 알 수 있으므로 return 값은 2명이다.