이코테 - 정확한 순위 with JAVA

 

 

해결

- 기본적으로 플로이드 워셜 알고리즘을 사용한다.

- 그래프를 만들어 노드 A, B 중 한쪽 방향으로만이라도 이동가능하면 두 사람은 비교 가능하다고 판단이 가능하다.

- 한 노드에서 모든 노드로 다 비교가 가능하면(한쪽 방향이라도 이동이 가능하다면) 정확한 순위를 알 수 있다.

 

실수

- (int)1e9는 비교가 가능하다.

- i, j 구분이 안되어서 실수를 했다.

- 한쪽 방향으로만이라도 라는 로직을 처리할 때, and 연산자를 사용하였다. 

 

 

 

 

 

코드

package JAVA.TCT.ShortestWay;


import java.util.*;

// 정확한 순위
public class Q2 {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[][] map = new int[n+1][n+1];
        for(int i=0; i<n+1; i++){
            for(int j=0; j<n+1; j++){
                map[i][j] = (int)1e9;
                if(i == j){
                    map[i][j] = 0;
                }
            }
        }
        for(int i=0; i<m; i++){
            int x = sc.nextInt();
            int y = sc.nextInt();
            map[x][y] = 1;
        }

        for(int i=1; i<n+1; i++){
            for(int x=1; x<n+1; x++){
                for(int y=1; y<n+1; y++){
                    map[x][y] = Math.min(map[x][y], map[x][i]+map[i][y]);
                }
            }
        }

        int result = 0;
        for(int i=1; i<n+1; i++){
            int count = 0;
            for(int j=1; j<n+1; j++){
                if(map[i][j] != (int)1e9 | map[j][i] != (int)1e9){
                    count += 1;
                }
            }
            if(count == n){
                result += 1;
            }
        }
        System.out.println(result);
    }
}