[Java] leetcode 997. Find the Town Judge

문제

https://leetcode.com/problems/find-the-town-judge/description/

Find the Town Judge - LeetCode

모든 사람의 신뢰를 받고, 그 자신은 아무도 믿지 않는 유니크한 한 사람을 찾는 문제. 

 

알아야 할 개념

• DFS
• 방향 그래프 indegree, outdegree 개념

풀이

주어진 조건을 그래프화 하였다. 로직은 다음과 같다. 

1. 우선 주어진 조건을 그래프화 한다.
2. 그래프 DFS 탐색을 하면서 현재 간선의 개수가 n-1 이고 왔던 길을 탐색 안하면 ok 

모든 간선을 탐색함으로 시간복잡도는 O(V * E ) 가 된다 .(정점개수 x 간선개수 )

 

 

O(N)으로 최적화된 풀이는 다음과 같다. 1.. n 에 대해 indegree, outdegree를 구한다. 

• indegree는 방향 그래프에서 자기 자신을 가리키는 간선의 개수이다 .
• outdegree는 방향 그래프에서 현재 정점에서 나가는 간선의 개수를 말한다. 

cur_v 의 ind 개수는 2, outd 개수는 3이다.

• indegree가 n-1 이고 outdegree가 0 인 지점을 리턴한다.

 

코드

자바

 

그래프 dfs 풀이

class Solution {
    public int findJudge(int n, int[][] trust) {
        HashSet<Integer> set =new HashSet<>();
        List<List<Integer>> l =new ArrayList<>();

        if(trust.length == 0 && n == 1)return 1;

        for(int i =0 ;i < n +1 ;i ++)
            l.add(new ArrayList<>());
        for(int x[] : trust){
            l.get(x[1]).add(x[0]);
            set.add(x[1]);
        }
        Queue<Integer> Q = new LinkedList<>();
        boolean v[] = new boolean[n+1];
        int cnt = 0;

        for(int s : set){
            Arrays.fill(v, false);
            Q.offer(s);
            v[s] = true;
            cnt = l.get(s).size();
            boolean flag = true;
            while(!Q.isEmpty() && flag){
                int size = Q.size();
                for(int i =0 ;i < size; i++){
                    int cur_v = Q.poll();
                    for(int nv : l.get(cur_v)){
                        if(nv == s){
                            flag = false;
                            break;
                        }else{
                            if(!v[nv])
                            Q.offer(nv);
                            v[nv] = true;
                        }
                    }
                    if(!flag)break;
                }
            }
            if(cnt == n-1 && flag)return s;
        }
        
        return -1;
    }
}

indegrees & outdegrees 풀이

class Solution {
    public int findJudge(int N, int[][] trust) {
        
        if (trust.length < N - 1) {
            return -1;
        }
        
        int[] indegrees = new int[N + 1];
        int[] outdegrees = new int[N + 1];

        for (int[] relation : trust) {
            outdegrees[relation[0]]++;
            indegrees[relation[1]]++; 
        }

        for (int i = 1; i <= N; i++) {
            if (indegrees[i] == N - 1)
            {
                if(outdegrees[i] == 0) return i;
                else return -1;
            }
        }
        return -1;
    }
}