문제

문제링크

접근

• 나보다 강한 사람, 약한 사람의 수가 n-1일 때 그 사람의 순위를 알 수 있다.
• 그래서 단방향 그래프를 이용해 강한 사람, 약한 사람을 dfs를 이용해 찾았다.
• 풀고 난 후 다른 분들은 플로이드-워셜 알고리즘을 이용한 사람들이 많았는데, 비슷한 시간복잡도와 실행시간을 가지더랑

풀이

import java.util.*;

class Solution {
    int size;
    Deque<Integer> stack = new ArrayDeque<>();
    public int solution(int n, int[][] results) {
        int answer = 0;
        size = n;
        List<Integer>[] stronger = new List[n+1];
        List<Integer>[] weaker = new List[n+1];
        for (int i = 1; i <= n; i++) {
            stronger[i] = new ArrayList<>();
            weaker[i] = new ArrayList<>();
        }
        
        for (int[] res : results) {
            stronger[res[0]].add(res[1]);
            weaker[res[1]].add(res[0]);
        }
        
        for (int i = 1; i <= n; i++) {
            if (getNextCnt(stronger, i) + getNextCnt(weaker, i) == n-1) answer++;
        }
        
        return answer;
    }
    
    private int getNextCnt(List<Integer>[] edges, int n) {
        int res = 0;
        boolean[] visited = new boolean[size+1];
        visited[n] = true;
        stack.push(n);
        
        while(!stack.isEmpty()) {
            for (Integer next : edges[stack.pop()]) {
                if (visited[next]) continue;
                res++;
                visited[next] = true;
                stack.push(next);
            }
        }
        
        return res;
    }
}