[JAVA] 프로그래머스 LEVEL3 순위

https://school.programmers.co.kr/learn/courses/30/lessons/49191

프로그래머스

코딩테스트 연습 > 그래프 > 순위

 

난이도: LEVEL3

알고리즘 유형: 그래프 - 위상 정렬 활용 

 

주석에 모든 내용을 기록

정답 코드 

import java.util.*;
class Solution {
    public int solution(int n, int[][] results) {
        // 위상을 기록한 input 
        int [] input = new int [n+1];
        // results -> 그래프
        ArrayList<Integer>[] graph = new ArrayList[n+1];
        // set[i]: i를 이긴 사람들 모음 
        Set<Integer>[] set = new HashSet[n+1];  
        // set2[i]: i가 이긴 사람들 모음  
        Set<Integer>[] set2 = new HashSet[n+1]; 
        // 초기화 작업 
        for(int i = 1; i <= n; i++){
            graph[i] = new ArrayList<>();
            set[i] = new HashSet<>();
            set2[i] = new HashSet<>();
        }
        // 그래프 연결 
        for(int [] result : results){
            int winner = result[0];
            int loser  = result[1];
            input[loser]++; 
            graph[winner].add(loser);
        }
        // 위상이 0인 정점들 큐에 추가 
        Queue<Integer> q = new LinkedList<>();
        for(int i = 1; i <= n; i++){
            if(input[i] == 0){
                q.add(i);
            }
        }
        // 위상 정렬 알고리즘 
        while(!q.isEmpty()){
            int cur = q.poll();
            for(int i = 0; i < graph[cur].size(); i++){
                int next = graph[cur].get(i);
                // 위상--
                input[next]--;
                // 본인이 가지고 있는 정점 추가 
                for(int temp : set[cur]){
                    set[next].add(temp);
                }
                // 본인 정점 추가 
                set[next].add(cur);
                // 만약 위상이 0이면 큐에 추가 
                if(input[next] == 0){
                    q.add(next);
                }
            }
        }
        // i가 이긴 사람들 set2에 추가 
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                if(i == j) continue;
                if(set[j].contains(i)){
                    set2[i].add(j);
                }
            }
        }
        // i가 이긴 사람들 + i가 진 사람들 == n - 1 순위 명확 
        int answer = 0;
        for(int i = 1; i <= n; i++){
            if(set[i].size() + set2[i].size() == n - 1) answer++;
        }
        return answer;
    }
}