[프로그래머스 알고리즘 고득점 Kit][그래프][Java] 순위

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

프로그래머스

 

1. 정답 코드

 

뭔가 스태틱 변수를 안쓰고 메서드로 분리하려다 보니 
복잡해졌는데
내가 이긴 사람 수와 내가 진 사람 수의 합이 나를 제외한 n-1 과 같으면 순위를 알 수 있다.
그래서 2개의 단방향 그래프를 기록하고 bfs 2번을 돌리는 식으로 계산했다.
모든 노드의 거리를 알 수 있는 플로이드 워셜로도 풀 수 있다.

import java.util.*;

class Solution {
    public int solution(int n, int[][] results) {
        ArrayList<Integer>[] winWay = new ArrayList[n+1];
        ArrayList<Integer>[] loseWay = new ArrayList[n+1];
        for(int i=1; i<=n; i++){
            winWay[i] = new ArrayList<>();
            loseWay[i] = new ArrayList<>();
        }
        for(int[] result : results) {
            int w = result[0];
            int l = result[1];
            winWay[w].add(l);
            loseWay[l].add(w);
        }
        int answer = 0;
        for(int i=1; i<=n; i++){
            if(isRanked(n, i, winWay, loseWay)) answer++;
        }
        return answer;
    }
    public boolean isRanked(int n, int player, ArrayList<Integer>[] win, ArrayList<Integer>[] lose) {
        boolean[] visited = new boolean[n+1];
        Queue<Integer> q = new ArrayDeque<>();
        int winCnt = count(q, win,visited, player);
        int loseCnt = count(q, lose, visited, player);
        
        return winCnt + loseCnt == n-1;
    }
    public int count(Queue<Integer> q, ArrayList<Integer>[] result, boolean[] visited, int player) {
        int cnt = 0;
        Arrays.fill(visited, false);
        visited[player] = true;
        q.add(player);
        while(!q.isEmpty()) {
            int curr = q.poll();
            for(int next : result[curr]) {
                if(visited[next]) continue;
                
                cnt++;
                visited[next] = true;
                q.add(next);
            }
        }
        return cnt;
    }
}