프로그래머스 순위

https://school.programmers.co.kr/tryouts/71895/challenges

프로그래머스의 순위이다.
이 문제를 풀기위해서는 순위가 정해지기 위해서는 다른 노드들간의 간선의 갯수가 총 자기 자신을 제외한 모든 순위를 알수 있어야한다. 따라서 이문제는 양방향으로 생각하는 것이아니라 그래프를 승리와 패배가 있는 두개의 그래프 상으로 생각해야한다.

import java.util.*;

class Solution {
    public void dfs(List<Set<Integer>> g, Set<Integer> visited, int index){
        Set<Integer> edges = g.get(index);
        
        if(g.get(index).size() == 0|| visited.containsAll(edges)){
            return;
        }
        
        for(int edge: edges){
            if(visited.contains(edge)){
                continue;
            }else{
                visited.add(edge);
                dfs(g,visited,edge);
            }
        }
    }
    public int solution(int n, int[][] results) {
        int answer = 0;

        
        List<Set<Integer>> winG = new ArrayList<>();
        List<Set<Integer>> loseG = new ArrayList<>();
        
        for(int i = 0; i <= n; i++){
            winG.add(new HashSet<>());
            loseG.add(new HashSet<>());
        }
        
        for(int i = 0; i< results.length; i++){
            winG.get(results[i][0]).add(results[i][1]);
            loseG.get(results[i][1]).add(results[i][0]);
        }
        
        List<Set<Integer>> dfsWin = new ArrayList<>();
        List<Set<Integer>> dfsLose = new ArrayList<>();
    
        for(int i = 0; i <= n; i++){
            dfsWin.add(new HashSet<>());
            dfsLose.add(new HashSet<>());
        }

        for(int i = 1; i <= n; i++){
            dfs(winG, dfsWin.get(i), i);
            dfs(loseG, dfsLose.get(i), i);
        }
       
        for(int i = 1; i <= n; i++){
            dfsWin.get(i).addAll(dfsLose.get(i));
            if(dfsWin.get(i).size() == n-1){
                answer++;
            }
        }
        
        return answer;
    }
}

그래프를 집합으로 두개를 선언한 것을 볼 수 있는데 사실 집합으로 선언할 필요는 없다.

 List<Set<Integer>> winG = new ArrayList<>();
 List<Set<Integer>> loseG = new ArrayList<>();

이후 경기 결과를 순회하면서 승리와 패배 그래프를 그려준 후
가장 중요한 과정인 DFS 를 거친다. 이렇게 이긴 그래프와 패배 그래프를 각노드에서 DFS 로 순회하게 된다면 직접적으로 result 배열에서 표시되었던 관계뿐만 아니라 다른 하나의 노드의 순위가 정해지면 상대적으로 정해진 자신의 순위조차 DFS 로 알 수 있게된다.

이렇게 DFS 로 자신이 방문했던 패배, 승리 집합을 합쳐서 방문한 노드의 갯수가 전체 노드에서 자신을 제외한 갯수라면 자신의 정확한 순위는 알수 있게된다.

   List<Set<Integer>> dfsWin = new ArrayList<>();
    List<Set<Integer>> dfsLose = new ArrayList<>();

    for(int i = 0; i <= n; i++){
        dfsWin.add(new HashSet<>());
        dfsLose.add(new HashSet<>());
    }

    for(int i = 1; i <= n; i++){
        dfs(winG, dfsWin.get(i), i);
        dfs(loseG, dfsLose.get(i), i);
    }
   
    for(int i = 1; i <= n; i++){
        dfsWin.get(i).addAll(dfsLose.get(i));
        if(dfsWin.get(i).size() == n-1){
            answer++;
        }
    }

위의 부분이 핵심 비지니스로직이므로 가장 중요하다.