[Programmers] #49191 - 순위 [Java][C++][Python]
1. 아이디어
일부 경기 결과만 주어졌을 때 순위를 정확히 알 수 있는 선수가 몇 명인지 세는 문제다. 선수들의 승패를 이긴 선수에서 진 선수로 가는 간선으로 보면, 실력이 좋은 선수는 항상 이기므로 A 선수가 B 선수를, B 선수가 C 선수를 이겼을 때 A 선수가 C 선수보다 실력이 좋아 직접 붙지 않았어도 A 선수가 C 선수를 이긴다고 알 수 있다. 즉 한 선수가 다른 선수를 이긴다고 알 수 있는 것은 이긴 선수에서 진 선수까지 간선을 따라 닿을 수 있는 것과 같고, 모든 선수 쌍의 도달 여부는 플로이드-워셜 알고리즘으로 구한다. $O(n^3)$이지만 $n \le 100$이라 충분하다.
순위를 구할 한 선수(기준 선수)의 순위는 그 선수보다 실력이 좋은 선수의 수에 1을 더한 값이다. 기준 선수를 이긴다고 알 수 있는 선수는 반드시 앞에, 기준 선수에게 진다고 알 수 있는 선수는 반드시 뒤에 서고, 승패를 알 수 없는 선수는 앞에 서는 선수를 이길 수도 뒤에 서는 선수에게 질 수도 없어(그랬다면 기준 선수와의 승패도 알 수 있다) 기준 선수의 앞에 서든 뒤에 서든 구한 승패와 모순이 없다. 그러므로 승패를 알 수 없는 선수가 있으면 그 선수들을 모두 뒤에 세운 순위와 모두 앞에 세운 순위가 달라 순위가 하나로 정해지지 않고, 기준 선수가 나머지 $n - 1$명 모두와 승패를 알 수 있을 때만 순위가 하나로 정해지므로 그런 선수의 수가 답이다.
2. 코드
풀이 [Java][C++][Python]
경유지 k를 가장 바깥 반복에 두었다. 안쪽에 두면 k를 거쳐야 이어지는 승패를 놓치는 경우가 생긴다.
승패를 세는 반복은 j가 i와 같은 경우도 훑었지만, 경기 결과에 모순이 없어 dp[i][i]는 참이 되지 않으므로 n - 1과 비교해도 된다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public int solution(int n, int[][] results) {
boolean[][] dp = new boolean[1 + n][1 + n];
for (int[] r : results) {
dp[r[0]][r[1]] = true;
}
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (dp[i][k] && dp[k][j]) dp[i][j] = true;
}
}
}
int ans = 0;
for (int i = 1; i <= n; i++) {
int cnt = 0;
for (int j = 1; j <= n; j++) {
if (dp[i][j] || dp[j][i]) cnt++;
}
if (cnt == n - 1) ans++;
}
return ans;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1 + 100;
bool dp[MAX_N][MAX_N];
int solution(int n, vector<vector<int>> results) {
for (auto& r : results) dp[r[0]][r[1]] = true;
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (dp[i][k] && dp[k][j]) dp[i][j] = true;
}
}
}
int ans = 0;
for (int i = 1; i <= n; i++) {
int cnt = 0;
for (int j = 1; j <= n; j++) {
if (dp[i][j] || dp[j][i]) cnt++;
}
if (cnt == n - 1) ans++;
}
return ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def solution(n, results):
dp = [[False] * (1 + n) for _ in range(1 + n)]
for u, v in results:
dp[u][v] = True
for k in range(1, n + 1):
for i in range(1, n + 1):
for j in range(1, n + 1):
if dp[i][k] and dp[k][j]:
dp[i][j] = True
ans = 0
for i in range(1, n + 1):
cnt = 0
for j in range(1, n + 1):
if dp[i][j] or dp[j][i]:
cnt += 1
if cnt == n - 1:
ans += 1
return ans