[LeetCode] 997. Find the Town Judge

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

Find the Town Judge - LeetCode

LeetCode - Find the Town Judge

문제 유형 : 그래프

문제 난이도 : Easy

 

문제

In a town, there are n people labeled from 1 to n. There is a rumor that one of these people is secretly the town judge.

If the town judge exists, then:

1. The town judge trusts nobody.
2. Everybody (except for the town judge) trusts the town judge.
3. There is exactly one person that satisfies properties 1 and 2.

You are given an array trust where trust[i] = [ai, bi] representing that the person labeled ai trusts the person labeled bi. If a trust relationship does not exist in trust array, then such a trust relationship does not exist.

Return the label of the town judge if the town judge exists and can be identified, or return -1 otherwise.

 

도시에 n명의 사람이 1부터 n까지 있다.

도시에는 숨겨진 town judge가 있는데, 다음의 조건을 만족한다:

1. town judge는 아무도 믿지 않는다.
2. town judge를 제외한 모두가 town judge를 신뢰한다.
3. 1번과 2번을 만족하는 사람은 단 하나뿐이다.

 

trust[i] = [ai, bi]의 형태로 주어진다.

ai가 bi를 신뢰한다는 뜻이다.

town judge의 번호를 구하시오.

없다면, -1을 반환하시오.

 

풀이

방향이 있는 그래프 문제와 같다.

진입차수를 담는 배열과, 진출차수를 담는 배열을 만든다.

각각의 신뢰 관계를 읽으면서 진입차수와 진출차수를 구한다.

진입차수[i] = n-1 && 진출차수[i] == 0인 번호를 구하면 된다.

 

코드

C++

class Solution {
public:
    int findJudge(int n, vector<vector<int>>& trust) {
        vector<int> indegree(n+1, 0);
        vector<int> outdegree(n+1, 0);

        for(const auto &t : trust) {
            indegree[t[1]]++;
            outdegree[t[0]]++;
        }

        int judge = -1;
        for(int i = 1; i <= n; i++) {
            if(indegree[i] == n-1 && outdegree[i] == 0) {
                judge = i;
                break;
            }
        }
        return judge;
    }
};

Go

func findJudge(n int, trust [][]int) int {
    indegree := make([]int, n+1)
    outdegree := make([]int, n+1)

    for _, t := range trust {
        indegree[t[1]]++
        outdegree[t[0]]++
    }

    judge := -1
    for i := 1; i <= n; i++ {
        if indegree[i] == n-1 && outdegree[i] == 0 {
            judge = i
            break
        }
    }

    return judge
}