Today I Learned

오늘도 랜덤한 lv.3 문제를 풀어봤다. 여러 시도를 하면서 난이도에 비해 시간을 꽤 들인 문제였다. 아직 문제 해결에 대한 발상이 좀 부족하다고 느낀다. 더 열심히하자!!

순위

문제

n명의 선수가 대회에 참가해 1~n의 번호를 받았다. 선수의 수 n과 1대1 경기결과 results가 주어진다. 이차원 배열 reuslts는 {이긴선수번호, 진선수번호}로 되어있다. 모든 경기 결과에서 모순은 없다고 할 때, 정확한 순위를 매길 수 있는 선수의 수를 구하라.

풀이 과정

1. 우선 주어진 경기 결과들 만으로 선수들 간의 상하관계를 만들어야 했다. 예를들어 1번 선수가 3번을 이기고, 3번이 5번을 이겼다면 주어진 문제에선 1번이 5번을 이겼다고 가정한다.

2. 모든 선수들의 다른 모든 선수에 대한 경기 결과를 유추해야 하므로 플로이드 워셜이 적절할 것이라 생각했다.

3. 우선 선수간의 승패 관계를 정리할 이차원 배열 graph 만든다. 그리고 results에 주어진 경기결과를 graph에 정리한다. graph[i][j]에서 i가 j에게 이기면 1, 지면 -1, 결과가 없으면 디폴트 값인 0이다.

4. 플로이드 워셜 알고리즘을 써서 i가 m을 이기고 m이 j를 이겼다면 graph[i][j] = 1을 넣고, 반대로 졌다면 -1을 넣게 한다.

5. 위의 과정으로 graph에 주어진 결과들을 활용해 선수들끼리 승패 관계가 정리된다.
   정확한 순위를 매길 수 있는 선수는 선수 i의 경기 결과가 있는 배열 graph[i]에서 자기자신의 결과를 제외한 나머지가 0이 아니어야한다. 즉, 각 행에서 0이 한개여야 순위를 정확하게 측정할 수 있다. 이중 for문으로 count가 1 일 경우만 체크해서 반환하면 문제가 풀린다.

구현 코드

class Solution {
    
    public void floydWarshall(int n, int[][] graph){
        for(int m=1; m<=n; m++){
            for(int i=1; i<=n; i++){
                for(int j=1; j<=n; j++){
                    if(graph[i][m]==1 && graph[m][j]==1){
                        graph[i][j] = 1;
                        graph[j][i] = -1;
                    }
                    if(graph[i][m]==-1 && graph[m][j]==-1){
                        graph[i][j] = -1;
                        graph[j][i] = 1;
                    }
                }
            }
        }
    }
    
    public int solution(int n, int[][] results) {
        int answer = 0;
        
        int[][] graph = new int[n+1][n+1];
        
        for(int[] r : results){
            int w = r[0];
            int l = r[1];
            graph[w][l] = 1;
            graph[l][w] = -1;
        }
        
        floydWarshall(n,graph);
        
        for(int i=1; i<=n; i++){
            int count = 0;
            for(int j=1; j<=n; j++){
                if(graph[i][j] == 0) count++;
            }
            if(count == 1) answer++;
        }
        
        return answer;
    }
}

배운 점

• 모든 노드의 다른 모든 노드에 대한 관계가 필요하면 플로이드 워셜을 쓰면 간단하다. 단, 시간복잡도가 O(V^3)이라 항상 이에대해선 생각해둬야 한다.

• 문제를 풀면서 여러 시도를 해보았고, 플로이드 워셜까진 스스로 떠올려 구현했으나 "정확한 순위를 매길 수 있는 선수의 수"를 구할 아이디어가 떠오르지 않아 힌트를 참고했다.
  정확한 순위는 다른 모든 관계가 있어야 구할 수 있다!