[Programmers] - 순위 (그래프) with Python

 

 

📎 간략한 문제 정리

• n명의 권투선수의 승패가 배열로 주어집니다. 이 배열에서 승패를 기준으로 순위를 매겼을 때, 위치가 확정되어있는 사람의 수를 구하는 문제입니다.

 

📈 문제 분석

• 예시의 배열을 분석해보면에서 4는 3번에게 이기고, 4는 또 2번에게 이기고, ... 2번은 5번에게 이깁니다. 이를 기준으로 생각해보면 2는 1, 3, 4에게 지고 5번에게 이기므로 반드시 4위에 위치합니다. 1을 제외하고 생각해보면 4, 3, 2, 5의 위치는 서로 결정이 되지만 1이 4 앞에 올 수도, 4와 3 사이에 올 수도, 그리고 3과 2 사이에 올 수 있으므로 1, 3, 4의 위치는 확정되지 않습니다.
• [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]]

 

🙋‍♂️ 내가 처음 생각한 해결 방법

• 처음에는 1차원 배열로 순위의 리스트를 정해놓고 그 빈칸에 채우는 가능성을 생각하며 가능성이 없는 요소들을 제거하려고 했습니다. 하지만 이렇게 되면 모든 경우에 항상 위치가 같은 요소를 찾는 일이 어려워집니다. 그래서 다른 블로그의 풀이를 참고하여 해결의 힌트를 얻었습니다.(하단에 주소)
• 풀이는 반복을 활용한 DFS로 어떤 사람 A를 기준으로 볼 때 B를 이겼다고 가정하면, B가 C를 이기는 경우 A는 반드시 C를 이기게 됩니다. 이러한 관계를 표로 작성하여 자신을 제외한 모든 사람과 관계가 확정된 사람은 위치가 고정됨을 알 수 있습니다. 즉, 순위가 결정되어 있다는 것은 단순히 1차원 배열에서 어느 위치를 의미하는 것이 아니라 모든 경우의 수를 탐색했을 때 자신을 제외한 모든 요소들과 관계가 정해져 있는 사람입니다.

 

💻 풀이한 코드

def solution(n, results):
    table = [[0 for _ in range(n)] for _ in range(n)]
    win, lost = 1, -1
    for winner, loser in results:
        table[winner-1][loser-1], table[loser-1][winner-1] = win, lost
    for me in range(n):
        losers = [index for index, cand in enumerate(table[me]) if cand == win]
        while losers:
            loser = losers.pop()
            for index, cand in enumerate(table[loser]):
                if cand == win and table[me][index] == 0:
                    table[me][index], table[index][me] = win, lost
                    losers.append(index)
    return len(["fixed" for i in range(n) if table[i].count(0) == 1])

 

📝 해결 과정에서 만난 문제, 고민들

• 이 문제를 해결하기 위해 문제를 한문장으로 재정의하면 "순위가 고정되어 있는 선수는 다른 모든 선수와의 관계가 정해져있다" 입니다. 위치가 애매하다는 의미는 서로 관계가 정해져있지 않은 선수가 있다는 의미이고, 그래서 선수 A가 이긴 선수 B를 기준으로, B가 이긴 선수는 A가 모두 이길 수 있기 때문에 추가 등록한다는 개념입니다. 이 때, 패배를 기준으로 작성할 수도 있겠지만 둘 중 한가지만 작성해도 됩니다. 왜냐하면 A가 B를 이길 경우 B의 입장에서는 패배이지만, 이미 A와의 관계를 설정할 때 패배가 기록되기 때문에 따로 패배를 기록할 필요는 없습니다.
• 중복이 없다는 전제 조건에서 집합을 사용하면 요소를 추가할 때 '|' 연산으로 간단하게 합집합을 생성할 수 있습니다.

 

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

https://velog.io/@tjdud0123/%EC%88%9C%EC%9C%84-python