순위와 DFS

DFS 문제는 왜 풀어도 풀어도 익숙해지지가 않지...

입출력 예시

[[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] -> 2

각 리스트에서 앞에 있는 선수가 뒤에 있는 선수를 이김. 경기결과는 서로 모순되지 않음. (예: 어느 경기에서는 1번 선수가 4번을 이겼는데, 1번 선수가 2번 선수에게 지고, 2번 선수는 4번 선수를 이김)

즉 어찌보면 이행성 (transitivity)가 성립됨...
그러나 모든 경기결과가 기록되지 않아서, 한 선수의 우위를 정하기 힘든 상황. (예: 1번 선수가 2번 선수를 이겼지만, 3, 4번 선수와의 우위를 가리지 않았음)

그래서 순위가 결정된 선수가 몇 명인지를 찾는 문제이다. 코딩테스트를 공부할 때는 항상 ChatGPT를 곁에 두고 쓰는 편 ㅎ.ㅎ

from collections import defaultdict

def solution(n, results):
    
    wins = defaultdict(set)
    loses = defaultdict(set)
    
    for winner, loser in results:
        wins[winner].add(loser)
        loses[loser].add(winner)

    def dfs(player, res):
        visited.add(player)
        
        for opponent in res[player]:
            if opponent not in visited:
                dfs(opponent, res)
        
    answer = 0
    
    for player in range(1, n+1):
        visited = set()
        
        dfs(player, wins) # 해당 선수가 이긴 선수
        dfs(player, loses) # 해당 선수가 진 선수
        
        if len(visited) == n:
            answer += 1
            
    return answer

각각의 승자, 패자 key-value쌍으로 존재하도록 wins와 loses dict을 생성한다.

처음엔 굳이...? 라고 생각했으나, 마지막 visited에서 모든 node, 즉 모든 선수와의 우위가 정해졌다면 visited의 길이가 n 총 선수의 수와 같다는 아이디어!

순위가 정해지지 않은 선수를 어떻게 조작적으로 정의해야 하는거지... 라는 생각에 막막했던 문제였다. 이행성을 적용했는데도 모든 선수와의 우위가 정해지지 않았다면 바로 그 선수가 순위를 알 수 없는 선수라는 것.

그리고 함수 안의 dfs 함수는 return값이 없는데, 선수들의 우위가 정해졌다는 visited를 체크한다.

아무튼 DFS 열심히 공부해야겠다...