[Programmers] 순위

난이도 : Level 3

문제링크

• n명의 권투선수가 대회에 참가하였다
• 1대1 방식으로 진행되며 승패 정보가 주어진다
  • 각 행 [A, B]는 A 선수가 B 선수를 이겼다는 의미입니다
  • A선수가 B선수보다 실력이 좋다면 A선수는 B선수를 항상 이깁니다
• 몇몇 경기가 분실되어 정확하게 순위를 매길 수 없습니다
• 정확하게 순위를 매길 수 있는 선수의 수를 리턴하라

 

해설

1. 플로이드-워셜 알고리즘을 활용한 모든 선수들의 승패 배열 생성하기

boolean[][] graph = new boolean[n][n];

for (int i = 0; i < results.length; i++) {
    graph[results[i][0]-1][results[i][1]-1] = true;
}

for (int k = 0; k < n; k++) {            
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (graph[i][k] && graph[k][j]) graph[i][j] = true;
        }
    }
}

• graph[i][j] : i가 j를 이겼을 경우 true
• 플로이드-워셜 알고리즘을 사용하여 승패배열 생성하기
  • if (graph[i][k] &&graph[k][j]) graph[i][j] = true;
  • i가 k를 이기고, k가 j를 이겼다면 i는 j를 이긴다.
  • A선수가 B선수보다 실력이 좋다면 A선수는 B선수를 항상 이기기 때문

 

2. 경기를 모두 치른 선수 구하기

for (int i = 0; i < n; i++) {
    int count = 0;
    for (int j = 0; j < n; j++) {
        if (graph[i][j] || graph[j][i]) count++;
    }
    if (count == n-1) answer++;
}

• 승패 배열을 탐색하면서 i라는 선수가 자신이 치러야 할 모든 경기를 소화하였는지 이기고 졌던 횟수를 카운트하여 확인한다.

 

 

블로그 참고

• kimdukbae - [알고리즘] 플로이드 워셜 알고리즘 (Floyd-Warshall Algorithm)