[프로그래머스/Graph] Level 3 순위 (JAVA)
문제
풀이
코드
import java.util.*;
class Solution {
private static final int WINNER = 0;
private static final int LOSER = 1;
private int n;
private List<List<Integer>> graph;
public int solution(int n, int[][] results) {
this.n = n;
initGraph(results);
return countRanked();
}
private void initGraph(int[][] results) {
graph = new ArrayList<>();
for (int i=0 ; i<=n ; i++)
graph.add(new ArrayList<>());
for (int[] result : results)
graph.get(result[WINNER]).add(result[LOSER]);
}
private int countRanked() {
int count = 0;
for (int i=1 ; i<=n ; i++)
if (isRanked(i)) count++;
return count;
}
private boolean isRanked(int target) {
return countUpper(target) + countLower(target) == n - 1;
}
private int countUpper(int target) {
boolean[] visited = new boolean[n+1];
Queue<Integer> uppers = new LinkedList<>();
uppers.offer(target);
int count = 0;
while(!uppers.isEmpty()) {
int current = uppers.poll();
visited[current] = true;
count++;
for (int i=1 ; i<=n ; i++)
if (graph.get(i).contains(current) && !visited[i]) {
visited[i] = true;
uppers.offer(i);
}
}
return count - 1;
}
private int countLower(int target) {
boolean[] visited = new boolean[n+1];
Queue<Integer> lowers = new LinkedList<>();
lowers.offer(target);
int count = 0;
while(!lowers.isEmpty()) {
int current = lowers.poll();
count++;
for (int lower : graph.get(current)) {
if (!visited[lower]) {
visited[lower] = true;
lowers.offer(lower);
}
}
}
return count - 1;
}
}
Author And Source
이 문제에 관하여([프로그래머스/Graph] Level 3 순위 (JAVA)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jwkim/graph-rank저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)