프로그래머스 순위 (JAVA)

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

프로그래머스

 

저는 bfs를 통해 문제를 해결하였습니다.

먼저 이기는 방향과 지는 방향으로 그래프를 저장하였습니다.

각각의 사람에서 bfs를 진행하면서 탐색하는 노드의 개수를 구하였습니다. 이 노드의 개수가 자신을 제외해서 n-1인지를 판별하고 같다면 결과값을 늘려 문제를 해결하였습니다.

 

import java.util.*;

class Solution {
    public int solution(int n, int[][] results) {
        int answer = 0;
        List<Integer>[] win = new List[n+1];
        List<Integer>[] lose = new List[n+1];
        for(int i = 0 ; i <= n ; i++){
            win[i] = new LinkedList<>();
            lose[i] = new LinkedList<>();
        }
        for(int[] result : results){
            win[result[0]].add(result[1]);
            lose[result[1]].add(result[0]);
        }
        for(int i = 1 ; i <= n ; i++){
            int cnt = 0;
            cnt += bfs(i,win,n);
            cnt += bfs(i,lose,n);
            if(cnt == n-1){
                answer++;
            }
        }
        return answer;
    }
    private static int bfs(int start, List<Integer>[] list, int n){
        Queue<Integer> q = new LinkedList<>();
        int cnt = 0;
        q.offer(start);
        boolean[] visited = new boolean[n+1];
        while(!q.isEmpty()){
            int now = q.poll();
            for(int next : list[now]){
                if(!visited[next]){
                    q.offer(next);
                    visited[next] = true;
                    cnt++;
                }
            }
        }
        return cnt;
    }
}