[프로그래머스]순위(Level 3)

📝문제 링크

프로그래머스 > 그래프 > 순위 문제보기

🔑문제 KeyPoint

DFS, BFS로 탐색을 한다고 해도 순위 판단은 불가능해보였다.
결국, 오늘도 구팀장에게 검색하여 도움을 받아서 해결해보았다.
이 문제는 플로리다 와샬 알고리즘을 적용해야 한다고 한다.

우선 Floyd Warshall 알고리즘부터 이해해보자. ▶플로리다 와샬 개념 이해하기

그래서 Floyd Warshall 알고리즘은 이해하고,
최종적으로 각 선수와 선수끼리의 전적을 배열로 나타냈다.

1. floyd warshall을 위한 2차원 배열 생성 : rank[n+1][n+1] (선수수와 인덱스를 맞추기위함)
   1-1. 자기자신과 싸우는 일은 없으니 0으로 설정, 나머지는 무한대로 설정
2. 상대와의 전적을 체크한다.
   2-1. 주어진 results[]로 이긴 경우 1로 설정 (단방향임을 주의!, 승패가 정해져있다.)
3. floyd warshall 알고리즘 적용

근데 도대체 순위는 어떻게 결정할 수 있는 것인가,,??😥😥😥
(플로리다 와샬 알고리즘을 이용한 풀이법을 찾아보았다!! 언제쯤 ㅎㅎ혼자 다 풀 수 있는 날이 올까😙)

✔ 우선 순위를 결정할 수 있는 경우는?
자기자신을 제외한 모든 선수와 경기를 한 경우에만 순위를 결정지을 수 있다.
이미 우린 floyd warshall로 모든 선수와의 경기전적을 구해놓았다.

4. 자기자신이 아니면서, 모든 선수와 경기를 한 경우의 수를 체크하면 정답이 나온다.

코드를 보면서 다시 한번 살펴보자.🔍

💻문제 풀이

public int solution(int n, int[][] results) {
    int[][] rank = new int[n+1][n+1];       // 인덱스 1부터 시작하려고
    int inf = 1000000;                      // 방문 불가능한 경우

    // 자기 자신과 싸우는 경우만 0으로 설정, 나머지는 inf로 초기화
    for(int i=1;i<n+1;i++){
        for(int j=1;j<n+1;j++){
            if(i==j)    rank[i][j] = 0;
            else        rank[i][j] = inf;
        }
    }

    // 상대 전적이 있는 경우 check
    // 단 방향으로만 체크해야한다. 승패가 정해져 있기 때문에
    for(int i=0 ; i< results.length; i++){
        rank[results[i][0]][results[i][1]] = 1;
    }

    // 플로리다 와샬 알고리즘으로 승부가 가능한 지 확인
    // k는 거쳐가는 사람
    for(int k=1;k<n+1;k++){
        // i는 나
        for(int i=1;i<n+1;i++){
            // j는 상대
            for(int j=1;j<n+1;j++){
                if(rank[i][j] > rank[i][k] + rank[k][j]){
                    rank[i][j] = rank[i][k] + rank[k][j];
                }
            }
        }
    }

    // 경기를 했는지 여부 체크
    boolean[] check = new boolean[n+1];
    // 모두 경기했다고 초기 설정
    Arrays.fill(check, true);
    // i는 나
    for(int i=1;i<n+1;i++){
        // j는 상대방
        for(int j=1;j<n+1;j++){
            // 나 자신과의 싸움이 아니면서, 서로 싸움을 한 전적이 없는 경우 false로 체크
            if(i != j && rank[i][j] == inf && rank[j][i] == inf){
                check[i] = false;
                break;              // 한 명이라도 싸움을 안했다면, i는 순위를 매길수 없기에 break문으로 빠져나옴
            }
        }
    }

    int answer=0;
    // 싸운적이 있는 사람만 count
    for(int i=1;i<n+1;i++){
        if(check[i])   answer++;
    }
    return answer;
}

전체 소스보기(git)

[참조]

순위 C++(그래프)[프로그래머스]