Graphs (싸이클탐지): 997. Find the Town Judge

997. Find the Town Judge

 

class Solution:
    def findJudge(self, n: int, trust: List[List[int]]) -> int:
        # 1. 그래프를 인접 리스트로 생성
        adj = {i: [] for i in range(1, n + 1)}  # 신뢰 관계
        for a, b in trust:
            adj[a].append(b)  # a가 b를 신뢰

        # 2. 판사 후보 선정
        # 판사는 누구도 신뢰하지 않아야 하므로, 신뢰 관계가 없는 노드를 후보로 선정
        candidates = [i for i in range(1, n + 1) if not adj[i]]

        if len(candidates) != 1:  # 후보가 1명이 아니면 판사 없음
            return -1

        candidate = candidates[0]

        # 3. 모든 사람이 후보를 신뢰하는지 확인
        trusted_count = 0
        for person in range(1, n + 1):
            if person != candidate and candidate in adj[person]:  # 후보가 신뢰받는지 확인
                trusted_count += 1

        # 후보가 n-1명의 신뢰를 받으면 판사, 그렇지 않으면 -1 반환
        return candidate if trusted_count == n - 1 else -1

 

https://youtu.be/QiGaxdUINJ8?si=P-SXmHNfuB4Ve_ds

 

 

class Solution:
    def findJudge(self, n: int, trust: List[List[int]]) -> int:        
        # 신뢰받는 횟수와 신뢰하는 횟수를 추적
        trust_received = defaultdict(int)  # 각 사람이 신뢰받은 횟수
        trust_given = defaultdict(int)  # 각 사람이 신뢰한 횟수

        # 신뢰 관계를 기록
        for src, dst in trust:
            trust_given[src] += 1
            trust_received[dst] += 1

        # 판사 후보를 찾기
        for i in range(1, n+1):
            # 본인은 누구도 신뢰하지 않고, n-1명에게 신뢰받는 사람을 판사로 선정
            if trust_given[i] == 0 and trust_received[i] == n-1:
                return i

        # 조건을 만족하는 판사가 없으면 -1 반환
        return -1