[코테연습] 2924. Find Champion II

문제 타입

• 그래프 탐색 문제
  • **Directed Acyclic Graph (DAG)**를 다루는 문제로, 간선을 따라 각 노드의 관계를 분석해야 함.
  • 특정 조건을 만족하는 "유일한 노드(챔피언)"를 판별하는 문제.
• 조건 기반 유일성 판별
  • 주어진 그래프에서 노드 간 관계를 통해 조건을 만족하는 유일한 노드를 찾음.

---

문제 분석

• 그래프 특성
  • n개의 팀(노드)과 edges 배열(간선)이 주어짐.
  • 간선 [u, v]는 u가 v를 이겼다는 것을 나타냄(방향성 존재).
  • 그래프는 사이클이 없는 DAG임.
• 챔피언 조건
  • 그래프의 "챔피언"은 패배한 적이 없는 노드여야 함.
    • 이 노드는 edges의 loser로 등장하지 않아야 함.
  • 그래프에 "유일한 챔피언"이 존재해야 함.
    • "무패 상태"인 노드가 여러 개라면 챔피언은 존재하지 않음(-1 반환).
• 결과 반환
  • "무패 상태"인 노드가 하나만 존재하면 해당 노드의 번호를 반환.
  • 그렇지 않으면 -1 반환.

---

문제 풀이

로직 설명:

• 1. isUndefeated 배열 생성
  • boolean[] isUndefeated를 사용하여 각 노드가 "무패 상태"인지 추적.
  • 초기에는 모든 노드를 true로 설정(모두 무패 상태로 가정).
• 2. 패배 기록 업데이트
  • edges를 순회하며, 각 간선의 loser를 false로 설정.
  • 패배한 노드는 "무패 상태"에서 제외됨.
• 3. 챔피언 후보 판별
  • isUndefeated 배열에서 true인 노드를 확인.
  • "무패 상태"인 노드가 여러 개면 -1 반환.
  • 하나뿐이라면 해당 노드 번호를 반환.

알고리즘:

1. 초기화:
   • 모든 노드를 "무패 상태"로 가정.
2. 패배 처리:
   • edges 배열을 순회하면서 패배한 팀을 false로 설정.
3. 결과 계산:
   • "무패 상태"인 노드의 개수를 확인.
   • 개수가 1개면 해당 노드 번호 반환, 아니면 -1 반환.

시간 복잡도:

• O(E + N):
  • E는 간선의 수, N은 노드의 수.
  • 간선 순회를 통해 패배를 기록(O(E)), 노드 배열을 탐색(O(N)).

공간 복잡도:

• O(N):
  • isUndefeated 배열을 위해 추가적인 공간 사용.

> java

 

import java.util.*;

class Solution {
    public int findChampion(int n, int[][] edges) {
        // 모든 팀이 "무패 상태"라고 가정하고 초기화
        boolean[] isUndefeated = new boolean[n];
        Arrays.fill(isUndefeated, true);
        
        // 간선을 순회하며 패배한 팀을 기록
        for (int[] edge : edges) {
            int winner = edge[0]; // 승리한 팀
            int loser = edge[1];  // 패배한 팀
            isUndefeated[loser] = false; // 패배한 팀은 "무패 상태"에서 제외
        }
        
        int champion = -1; // 챔피언 후보 초기화
        int championCount = 0; // "무패 상태"인 팀의 수

        // 무패 상태인 팀을 확인
        for (int team = 0; team < n; team++) {
            if (isUndefeated[team]) {
                champion = team; // 무패 상태인 팀을 챔피언 후보로 설정
                championCount++; // 무패 상태 팀 개수 증가
            }
        }
        
        // 무패 상태인 팀이 하나뿐이면 그 팀을 반환, 아니면 -1 반환
        return championCount == 1 ? champion : -1;
    }
}

 

> python

 

class Solution:
    def findChampion(self, n: int, edges: List[List[int]]) -> int:
        undefeated = [True] * n
        for edge in edges :
            winner = edge[0]
            loser = edge[1]
            undefeated[loser] = False
        
        champion = -1
        champion_count = 0

        for i in range(n) : 
            if undefeated[i] :
                champion=i
                champion_count+=1
        
        
        return champion if champion_count == 1 else -1