손가락놀이터

문제후기

1. 문제에서 n이 1이상 100이하인 것과 경기 결과가 1개 이상 4,500개 이하인 것을 보고 완전탐색이 가능하다고 판단했습니다.
2. 입출력 예시에서처럼 5번 선수는 다른 선수와 경기를 하지 않아도 2번 선수를 통해서 결과를 유추할 수 있다는 것을 확인할 수 있습니다.
3. A선수가 B선수를 이기고 B 선수가 C선수를 이긴다면 A가 C를 이긴다는 조건이 성립합니다.( A>B이고 B > C이면 A>C)
4. 유추를 통해 이길 수 있는 선수와 지는 선수를 set 집합을 통해 저장 후 결과를 추출했습니다.

문제링크

def solution(n, results):
    # 선수 경기 결과 hash로 저장
    matrix = dict()

    # 이기는 사람 집합과 지는 사람 집합
    for i in range(1, n + 1):
        matrix[i] = [set(), set()]

    # 경기 결과 입력
    for i in results:
        matrix[i[0]][0].add(i[1])
        matrix[i[1]][1].add(i[0])

    # 만약 A > B 이고 B > C 인경우 A>C인 관계(>는 이긴다)
    # 모든 선수를 통해 경기하지 않아도 결과를 아는 경우 저장.
    for num, match in matrix.items():
        if match[0] and match[1]:
            for win in match[0]:
                matrix[win][1].update(match[1])
            for lose in match[1]:
                matrix[lose][0].update(match[0])

    # 만약 이기는 경우, 지는 경우, 자기 자신의 합이 모든 선수의 수인 경우 +1
    answer = 0
    for num, match in matrix.items():
        if len(match[0]) + len(match[1]) + 1 == n:
            answer += 1
    return answer