[프로그래머스(파이썬/Python)] 순위

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

코딩테스트 연습 - 순위

 

이 문제를 해석할 때 가장 중요한 포인트는 "어떤 상황에서 순위가 결정되는가?"에 대한 이해입니다.

 

순위가 결정되려면 자신이 결투를 해서 이기는 사람, 지는 사람을 카운트할 때 자신을 제외한 n-1명의 정보가 모두 있어야 합니다.

 

따라서 results 배열로 주어진 승패 정보를 통해 먼저 각 사람이 이길 수 있는 사람 리스트를 DFS 탐색으로 만들 수 있고, 이 리스트를 바탕으로 역으로 생각해볼 때 이긴 사람의 리스트에 포함된 사람은 해당 사람에게 진 사람이 되기 때문에 진 사람의 리스트 목록 역시 만들 수 있죠.

 

최종적으로 "이기고, 진 기록의 리스트의 원소 개수를 더해서 n-1이 되는가?"의 여부로 답을 도출할 수 있습니다.

 

[풀이]

def dfs(winner, graph, results, visited, winning_result):
    visited[winner] = True
    for loser in graph[winner]:
        if not visited[loser]:
            winning_result.append(loser)
            dfs(loser, graph, results, visited, winning_result)


def solution(n, results):
    # 각 선수가 승리한 사람을 기록한 그래프
    graph = [[] for _ in range(n+1)]

    for result in results:
        win, lose = result[0], result[1]
        graph[win].append(lose)

    result_board = [[[], []] for _ in range(n+1)]

    # dfs 수행하면서 각 사람이 이긴 사람을 리스트에 추가
    for i in range(1, n+1):
        visited = [False] * (n+1)
        winning_result = []
        dfs(i, graph, results, visited, winning_result)
        result_board[i][0] = winning_result

    answer = 0
    # 각 선수가 누구에게 패배했는지를 역으로 기록
    for i in range(1, n+1):
        for w in result_board[i][0]:
            result_board[w][1].append(i)

    # 각 사람이 이기고 진 결과 내용이 n-1개라면 순위 정하기 가능
    for i in range(1, n+1):
        if len(result_board[i][0]) + len(result_board[i][1]) == n-1:
            answer += 1

    return answer