코딩하는 두꺼비

programmers.co.kr/learn/courses/30/lessons/49191

python으로 코테를 준비할 때 고득점 킷/그래프 이론에서 풀었던 문제이다. 처음 접근법을 생각해내긴 했는데 그것을 잘 가공해서 구현을 했어야 했는데 그걸 실패해 결국 다른 사람의 풀이를 보고 풀 수 있었다.

파이썬 set의 활용에 대해서 좀 더 공부하면 좋을 것 같다.

이 문제에서 중요한 것은 인접행렬과 비슷하게 승리와 패배 셋을 잘 만들어주고(A가 B를 이겻다면 A의 승리셋에 B를 넣어주고 B의 패배셋에 A를 넣어준다.)

승 갯수와 패 갯수가 n-1이 되는 사람이 답이라는 것을 캐치하는 것이 중요한 것 같다.

def solution(n, results):
    answer = 0
    win = {x:set() for x in range(1, n+1)}
    lose = {x:set() for x in range(1, n+1)}
    for a, b in results:
        win[a].add(b)
        lose[b].add(a)
    
    for i in range(1, n+1):
        for winner in lose[i]:
            win[winner].update(win[i])
        for loser in win[i]:
            lose[loser].update(lose[i])
            
    for i in range(1, n+1):
        if len(win[i]) + len(lose[i]) == n-1:
            answer += 1
    
    return answer