#054 · BFS/DFS중간DFS / 방향 그래프 탐색

최대 영향력 직원

문제

사내에 N명의 직원이 있고, 일부 직원들 사이에 단방향 멘토 관계가 있습니다. A → B 관계는 "A가 B에게 직접 영향을 준다"는 의미이며, 영향은 전파됩니다. (A→B, B→C이면 A는 C에게도 간접 영향)

가장 많은 직원에게 영향을 줄 수 있는 직원의 영향력(명 수)을 반환하세요. (자기 자신은 포함하지 않습니다)

n=5, edges=[[1,2],[1,3],[2,4],[3,4],[4,5]]
→ 4 (직원 1은 2,3,4,5에게 영향)

시간 복잡도 목표: O(N × (N + E))

예시 1: 직원1이 2,3,4,5 영향 → 4

입력: n = 5, edges = [[1,2],[1,3],[2,4],[3,4],[4,5]]

출력: 4

예시 2: 순환 구조 → 각자 2명에게 영향 → 2

입력: n = 3, edges = [[1,2],[2,3],[3,1]]

출력: 2

예시 3: 연결 없음 → 0

입력: n = 4, edges = []

출력: 0

예시 4: 분리된 두 쌍 → 각 1명 영향 → 1

입력: n = 4, edges = [[1,2],[3,4]]

출력: 1

예시 5: 직원1이 모두에게 직접 영향 → 4

입력: n = 5, edges = [[1,2],[1,3],[1,4],[1,5]]

출력: 4

solution.ts

에디터 로딩 중…

▶ 실행은 기록 없이 채점만, 제출은 결과가 진행률·오답노트에 기록됩니다.