https://school.programmers.co.kr/learn/courses/30/lessons/49191
n명의 권투선수가 권투 대회에 참여했고 각각 1번부터 n번까지 번호를 받았습니다. 권투 경기는 1대1 방식으로 진행이 되고, 만약 A 선수가 B 선수보다 실력이 좋다면 A 선수는 B 선수를 항상 이깁니다. 심판은 주어진 경기 결과를 가지고 선수들의 순위를 매기려 합니다. 하지만 몇몇 경기 결과를 분실하여 정확하게 순위를 매길 수 없습니다.
선수의 수 n, 경기 결과를 담은 2차원 배열 results가 매개변수로 주어질 때 정확하게 순위를 매길 수 있는 선수의 수를 return 하도록 solution 함수를 작성해주세요.
- 선수의 수는 1명 이상 100명 이하입니다.
- 경기 결과는 1개 이상 4,500개 이하입니다.
- results 배열 각 행 [A, B]는 A 선수가 B 선수를 이겼다는 의미입니다.
- 모든 경기 결과에는 모순이 없습니다.
import java.util.*;
class Solution {
static HashMap<Integer, ArrayList<Integer>> map;
public static int solution(int n, int[][] results) {
makeMap(n, results);
int[][] distance = new int[n + 1][n + 1];
for(int player = 1; player <= n; player++) dijkstra(player, distance[player]);
int answer = 0;
for(int player = 1; player <= n; player++) {
boolean flag = true;
for(int other = 1; other <= n; other++) {
if(other == player) continue;
if(distance[player][other] == Integer.MAX_VALUE && distance[other][player] == Integer.MAX_VALUE) {
flag = false;
break;
}
}
if(flag) answer++;
}
return answer;
}
static void makeMap(int n, int[][] results) {
map = new HashMap<>();
for(int player = 1; player <= n; player++) map.put(player, new ArrayList<>());
for(int[] result : results) {
int win = result[0], lose = result[1];
map.get(lose).add(win);
}
}
static void dijkstra(int player, int[] distance) {
Arrays.fill(distance, Integer.MAX_VALUE);
distance[player] = 0;
PriorityQueue<Edge> queue = new PriorityQueue<>();
queue.offer(new Edge(player, 0));
while(!queue.isEmpty()) {
Edge cur = queue.poll();
if(distance[cur.player] < cur.weight) continue;
for(int next : map.get(cur.player)) {
if(distance[next] > distance[cur.player] + 1) {
distance[next] = distance[cur.player] + 1;
queue.offer(new Edge(next, distance[next]));
}
}
}
}
static class Edge implements Comparable<Edge> {
int player, weight;
public Edge(int player, int weight) {
this.player = player;
this.weight = weight;
}
public int compareTo(Edge e) {
return weight - e.weight;
}
}
}