[그래프] 프로그래머스 Lv3. 순위 - Python

🗂️ 문제

링크: https://school.programmers.co.kr/learn/courses/30/lessons/49191#

프로그래머스

 

💡 접근법

lose_list[i] → i번 선수에게 진 선수들의 리스트와 win_list[i] → i번 선수에게 이긴 선수들의 리스트를 각각 구한다.

즉, 단방향 그래프 형식으로 이긴 선수들의 그래프와 진 선수들의 그래프 관계를 나타냈다.

 

i번 선수에게 이긴 선수들과 i번 선수에게 진 선수들을 모두 구한다.

만약 순위를 매길 수 있다면, lose_list[i]의 수 + win_list[i]의 수는 n-1일 것이다.

 

이를 구하기 위해 먼저 win_list를 완성해야 한다.

1. i번 선수에게 진 선수들로부터 i번 선수에게 진 선수들에게 진 선수들을 확인한다. i번 선수에게 진 선수들에게 진 선수들 모두 i번 선수에게 지는 것이 되기 때문이다.
2. 만약 확인된 선수가 i번 선수에게 진 선수들 리스트에 없다면, 리스트에 추가해주고 바뀐 리스트를 큐에 추가한다. 바뀐 경우에 대해 모든 선수들에게 다시 반영해야하기 때문이다.
3. 만약 큐가 비었다면, 모든 선수들에 대해 모든 계산이 끝난 것이다.

lose_list도 비슷한 방식으로 완성하고, 최종 값을 구한다.

 

😎 내 코드

from collections import deque

def solution(n, results):
    answer = 0
    
    lose_list = [[] for _ in range(n+1)]  # lose_list[i]: i번 선수에게 진 선수들
    for w, l in results:
        lose_list[w].append(l)
    
    queue = deque([])
    for i, w in enumerate(lose_list):
        if w:  queue.append((i, w))

    while queue:
        w, lose_people = queue.popleft()
        for lose in lose_people:  # i번 선수에게 진 선수들
            for l in lose_list[lose]:  # i번 선수에게 진 선수에게 진 선수들
                if l not in lose_list[w]:  # i번 선수에게 진 선수 리스트에 해당 선수가 없다면
                    lose_list[w].append(l)  # 리스트에 해당 선수 추가
                    queue.append((w, lose_list[w]))  # 큐에 (i, i번 선수에게 진 선수들) 추가
    
    
    win_list = [[] for _ in range(n+1)]  # win_list[i]: i번 선수에게 이긴 선수들
    for w, l in results:
        win_list[l].append(w)
    
    queue = deque([])
    for i, l in enumerate(win_list):
        if l:  queue.append((i, l))
    
    while queue:
        l, win_people = queue.popleft()
        for win in win_people:  # i번 선수에게 이긴 선수들
            for w in win_list[win]:  # i번 선수에게 이긴 선수를 이긴 선수들
                if w not in win_list[l]:  # i번 선수에게 이긴 선수 리스트에 해당 선수가 없다면
                    win_list[l].append(w)  # 리스트에 해당 선수 추가
                    queue.append((l, win_list[l]))  # 큐에 (i, i번 선수에게 이긴 선수들) 추가
    
    
    for w, l in zip(win_list, lose_list):
        if len(w) + len(l) == n-1:
            answer += 1
    
    return answer