LV 3: 순위

문제 링크

LV 3: 순위

구현 방식

• 각 노드에서, 자신의 노드를 포함하여 자신을 이긴 노드와 자신에게 진 노드의 개수가 n+1이 된다면 정확하게 순위를 매길 수 있다는 아이디어를 참고했다
  
  
• win_graph는 key - value의 관계가 '이긴 선수 - 진 선수'인 그래프이다
• lose_graph는 key - value의 관계가 '진 선수 - 이긴 선수'인 그래프이다
  
  
• win_graph를 bfs 탐색하면서 각각 본인을 이긴 노드를 저장해주어야 하는데, 이 때 set을 value로 갖고 있는 dictionary 형태의 자료형을 이용해주었다
  • win_nodes는 각 노드별 본인을 이긴 노드들을 저장하는 dictionary
  • lose_nodes는 각 노드별 본일이 이긴 노드들을 저장하는 dictionary
    
    
• bfs 탐색 과정에서 한가지 주의해줘야할 부분이, individual_nodes에 값을 add 해줄 때, 1) 매번 queue에서 popleft해준 curr 노드를 add 해주고, 2) 현재 element에 curr과 관련된 모든 노드들을 add 해줘야한다

코드

from collections import deque

def solution(n, results):
    
    def bfs(start, graph, individual_nodes):
        queue = deque([]); queue.append(start)
        visit = [False] * (n+1); visit[start] = True
        
        while queue:
            curr = queue.popleft()
            individual_nodes[curr].add(curr)
            
            if curr not in graph: continue
            
            for element in graph[curr]:
                if not visit[element]:
                    visit[element] = True
                    queue.append(element)
                    for c in individual_nodes[curr]:
                        individual_nodes[element].add(c)
        
    
    win_graph = dict(); lose_graph = dict()
    for result in results:
        w, l = result
        if w in win_graph: win_graph[w].append(l)
        else: win_graph[w] = [l]
        if l in lose_graph: lose_graph[l].append(w)
        else: lose_graph[l] = [w]
    
    win_nodes = dict(); lose_nodes = dict()
    for i in range(1, n+1):
        win_nodes[i] = set(); lose_nodes[i] = set()
    
    for i in range(1, n+1):
        bfs(i, win_graph, win_nodes)
        bfs(i, lose_graph, lose_nodes)
    
    answer = 0
    for i in range(1, n+1):
        if len(win_nodes[i]) + len(lose_nodes[i]) == n+1: answer += 1
    return answer