순위 - 플로이드 와샬

플로이드 와샬 알고리즘으로 푸는 문제입니다.

 

다익스트라 알고리즘의 경우에는 하나의 정점에서 출발했을 때 다른 모든 정점으로의 최단 경로를 구하는 것입니다.

참고: spacefordeveloper.tistory.com/172

다익스트라 알고리즘

플로이드 와샬 알고리즘의 경우에는 '모든 정점'에서 '모든 정점'으로의 최단 경로를 구하게 됩니다. 다익스트라 알고리즘은 현재 노드에서 가장 적은 가중치로 연결된 노드를 골라서  탐색을 해 나간다면 플로이드는 거쳐가는 정점을 기준으로 알고리즘을 수행하게 됩니다.

 

1. 이차원 배열에 정점에서 정점으로의 가중치를 저장을 해둔다.

 

2. 이차원 배열을 갱신을 해주는데 이때 거쳐가는 노드를 기준으로 갱신을 해준다. 

노드1을 거쳐가는 경우 , 노드2를 거쳐가는경우... 노드n 을 거쳐가는경우 이런식으로 갱신을 해준다.

3. 갱신을 하는 기준은 만약 노드1을 거쳐가게 된다면 노드2->3 vs 노드2->노드1 + 노드1 -> 노드3 이런식으로 비교를 한 다음에 이중 더 작은 값으로 교체가 됩니다.

 

 

blog.naver.com/ndb796/221234427842

24. 플로이드 와샬(Floyd Warshall) 알고리즘

 

이문제에서 플로이드 와샬을 통해 풀수 있는 이유는 A<B , B<C 이면 A<C 이다. 혹은 A>B,  B>C 이면 A>C이다라는 우원리를 이용할 수 있기 때문입니다. 플로이드 와샬은 아까 말했다시피 거쳐가는 노드를 기준으로 보게 됩니다. 거쳐가는 노드를 B를 통해서 A와B 의 관계 그리고 B와C의 관계를 파악하고 A<C 라는 결론을 얻을 수 있습니다. 플로이드 와샬에서는 실제로 최단거리를 구할때 사용하지만 이문제에서는 약간의 변형을 통해 거쳐가는 노드를 기준으로 이겼는지 졌는지의 결과를 파악하는데 쓰입니다.

 

<c++ 코드>

#include <string>
#include <vector>
#include <map>
using namespace std;
int answer = 0;


enum{LOSE = -1, NO, WIN};

int solution(int n, vector<vector<int>> results) {

    vector<vector<int>>arr(n+1,vector<int>(n+1,NO));
   
   //승패결과 n*n 테이블 만들기
    for(int i=0; i<results.size(); i++){
       int winner = results[i][0];
       int loser = results[i][1];
        arr[winner][loser] = WIN;
        arr[loser][winner]=LOSE;
    }
    
    for(int k=1; k<=n; k++){
        for(int from=1; from<=n; from++){
            
            if(arr[from][k]==NO){continue;}
            
            for(int to =1; to<=n; to++){
                
                if(arr[k][to]==NO){continue;}
                
                if(arr[from][k]==arr[k][to]){
                    arr[from][to]=arr[from][k];
                }
            }
        }
    }
    
    int answer = n;
    
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            if(i==j){continue;}
            if(arr[i][j]==NO){ //자기자신과 다른 노드 중 하나라도 관계성립이 안되면 순위로 정할 수 있는 노드가 아니기 때문에 answer--를 해줌
                answer--;
                break;
            }
        }
    }
    
    return answer;
}

<Java 코드>

 

class Solution {
    final static int NO = 0;
    final static int WIN = 1;
    final static int LOSE = 2;
    public int solution(int n, int[][] results) {
        int answer = 0;
        int[][] arr = new int[n+1][n+1];
        
        for(int i=0; i<results.length; i++){
            int winner = results[i][0];
            int loser = results[i][1];
            arr[winner][loser] = WIN;
            arr[loser][winner] = LOSE;
        }
        
        for(int k=1; k<=n; k++){
            for(int i=1; i<=n; i++){
                if(arr[i][k]==NO){continue;}
                for(int j=1; j<=n; j++){
                    if(arr[k][j]==NO){continue;}
                    if(arr[i][k]==arr[k][j]){
                        arr[i][j] = arr[i][k];
                    }
                }
            }
        }
        
        answer = n;
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                if(i==j){continue;}
                if(arr[i][j]==NO){
                    answer--;
                    break;
                }
            }
        }
        
        
        return answer;
    
}
}