LeetCode 997 - Find the Town Judge (Easy)

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

// LeetCode 997 - Find the Town Judge (Easy)
// https://leetcode.com/problems/find-the-town-judge/
// (같은 발상의 수업 문제: 백준 5622 다이얼 — 룩업 테이블에 최종 값을 곧장 박기
//  / 백준 7785 회사에 있는 사람 — 존재 여부를 배열 하나에 눌러 담기)

// 문제 설명
// 1 ~ n 번 사람. 마을 재판관은 (1) 아무도 안 믿고 (2) 자기 빼고 전원이 그를 믿고
// (3) 그런 사람이 정확히 한 명인 사람이다.
// trust[i] = {a, b} 는 "a가 b를 믿는다". 재판관 번호를 반환하고, 없으면 -1.

// 제약 조건
// 1 <= n <= 1,000, 0 <= trust.length <= 10,000
// 모든 쌍은 유일, a != b (자기 자신을 믿는 쌍은 없다), 1 <= a, b <= n

// Example
// Input : n=3, trust={{1,3},{2,3}}
// Output: 3       (3은 아무도 안 믿고 1,2가 3을 믿는다)
//
// Input : n=3, trust={{1,3},{2,3},{3,1}}
// Output: -1      (3이 1을 믿어 조건 (1) 위반)
//
// Input : n=1, trust={}
// Output: 1       (아무도 안 믿고 "나머지 0명"이 믿으므로 조건을 그냥 만족)

// 접근 — 조건을 차수로 번역하면 탐색이 사라진다
// 1) 간선 목록이 주어졌지만 인접 리스트도 방문 배열도 탐색도 필요 없다. 조건이 전부 차수로 번역된다.
//      조건 (1) 아무도 안 믿음 = 나가는 간선 0개   (outdegree == 0)
//      조건 (2) 전원이 믿음    = 들어오는 간선 n-1개 (indegree == n - 1)
//    둘 다 "그 사람 하나만 보면 판정"되므로 경로를 따라갈 이유가 없다 → 한 번 훑기 O(n + E).
// 2) in[]/out[] 두 배열 대신 cnt[] 하나에 (indegree - outdegree)를 바로 누적한다.
//    5622 다이얼에서 "숫자"가 아니라 "최종 걸리는 초"를 테이블에 직접 박아둔 것과 같은 발상 —
//    중간 표현을 만들지 않고 판정에 쓸 값을 곧장 쌓는다. 판정은 cnt[i] == n - 1 한 줄.
// 3) 이 압축이 안전한 이유: indegree <= n-1 이고 outdegree >= 0 이므로
//    cnt = in - out == n-1 이 되려면 in 이 최대치 n-1 이면서 동시에 out 이 최소치 0 이어야만 한다
//    → 조건 (1)(2)와 정확히 동치이고 오탐이 없다. 유일성(조건 3)도 자동 —
//    두 명이 동시에 out == 0 이면 서로를 믿지 않으므로 둘 다 in == n-1 일 수 없다.
// 4) 함정 n = 1: trust 가 비면 cnt[1] == 0 이고 n - 1 == 0 이라 판정식이 그대로 참 → 답은 1.
//    직관("믿어주는 사람이 없는데 재판관?")과 어긋나지만 차수 방식은 분기 없이 통과한다.
// 5) 사람 번호가 1-indexed 다. 0부터 돌리면 cnt[0] 쓰레기값이 n-1 과 겹칠 수 있으니
//    초기화 루프와 판정 루프 모두 1 ~ n 으로 맞춘다. 다중 케이스 대비 리셋도 그 범위만.
// 시간 O(n + E), 공간 O(n) — 정렬도 탐색도 없다

#include <vector>

using namespace std;

int cnt[1004];                           // (indegree - outdegree), 1-indexed (n <= 1000, 여유분 +4)

class Solution {
public:
    int findJudge(int n, vector<vector<int>>& trust)
    {
        for (int i = 1; i <= n; i++)
            cnt[i] = 0;                  // 다중 케이스 대비 — 1 ~ n 만 쓴다

        for (auto t : trust)
        {
            cnt[t[0]]--;                 // 믿은 쪽: outdegree
            cnt[t[1]]++;                 // 믿긴 쪽: indegree
        }

        for (int i = 1; i <= n; i++)
            if (cnt[i] == n - 1)         // in == n-1 && out == 0 을 한 번에 판정
                return i;

        return -1;
    }
};

정리

• 간선 목록이 주어졌다고 탐색 문제인 건 아니다. 그래프 탐색 문제(1971 BFS, 547 DFS)를 풀고 나면 trust[i] = {a, b}만 봐도 손이 인접 리스트로 가는데, 조건이 “그 정점 하나만 보면 판정되는” 형태(차수·개수)로 번역되면 탐색은 증발한다. 자료구조를 꺼내기 전에 조건을 그래프 용어로 옮겨 보는 게 먼저다.
• 상한·하한을 쓰면 조건 여러 개가 등식 하나로 접힌다. indegree ≤ n−1, outdegree ≥ 0이라는 사실 때문에 in − out == n−1이 조건 1·2와 동치가 되고, 배열 두 개가 int cnt[] 하나로 줄어든다. 접기 전에 오탐 불가를 짧게라도 확인해 두면 마음 놓고 쓸 수 있다.
• 조건 3(유일성)을 따로 검사하지 않아도 되는 근거도 같은 상한에서 나온다. 두 사람이 동시에 outdegree == 0이면 서로를 믿지 않으므로 각자 들어오는 간선이 하나씩 비어 둘 다 n−1을 못 채운다. 그래서 루프에서 처음 찾은 i를 바로 반환해도 안전하다.
• 잘 접힌 판정식은 엣지 케이스를 따로 안 짚어도 통과한다. n = 1의 답이 1이라는 게 직관에 안 맞아도 cnt[1] == 0 == n-1로 그냥 맞는다. 특수 케이스 if가 필요해지면 접는 방식을 잘못 골랐다는 신호일 수도 있다.
• 남은 함정은 형식 쪽이다. 1-indexed라 초기화·판정 루프를 1 ~ n으로 맞춰야 하고, 전역 배열은 1971·547과 같은 이유로 매 호출 리셋한다. a != b 제약이 있어 자기 루프 예외도 필요 없다 — 만약 a == b가 허용됐다면 cnt[a]에서 --와 ++가 상쇄돼 조건 1을 조용히 빠져나가는 사람이 생겼을 것이다.
• 검증: 예제 3개 + n=1 + 재판관 없는 체인 + 다수 신뢰 케이스를 n=1000(최대) → 예제 3 → n=1 → 예제 1 → 체인 → 예제 2 순서로 이어 호출해 6/6 통과 (MSVC /std:c++17 컴파일·실행).

핵심 요약 — 재판관 조건은 “아무도 안 믿음 = outdegree == 0”, “전원이 믿음 = indegree == n-1“로 번역되므로 탐색이 아예 필요 없고, cnt[] 하나에 (in − out)을 누적하면 판정이 cnt[i] == n - 1 한 줄이 된다. in ≤ n-1·out ≥ 0이라는 상한 덕에 이 한 줄이 두 조건과 동치이고 유일성까지 따라오며, n = 1이면 답이 1이라는 반직관 케이스도 분기 없이 통과한다.