[프로그래머스 | 파이썬 python] 순위

그래프 | BFS

🌏 문제

프로그래머스

 

 

👽 풀이 ➡️ BFS 이용

자신이 이긴 선수 + 진 선수의 합이 n-1이 되는 경우 순위를 알 수 있다고 할 수 있다.

from collections import deque
def solution(n, results):
    answer = 0
    graph = [[] for _ in range(n+1)]
    graph1 = [[] for _ in range(n+1)]
    
    for result in results:
        a,b = result
        graph[a].append(b)
        graph1[b].append(a)
    
    def win(cur):
        queue = deque()
        queue.append(cur)
        visited = [0 for _ in range(n+1)]
        total = 0
        
        while queue:
            cur = queue.popleft()
            for i in graph[cur]:
                if visited[i] == 0:
                    visited[i] = 1
                    queue.append(i)
                    total += 1
        
        return total
    
    def lose(cur):
        queue = deque()
        queue.append(cur)
        visited = [0 for _ in range(n+1)]
        total = 0
        
        while queue:
            cur = queue.popleft()
            for i in graph1[cur]:
                if visited[i] == 0:
                    visited[i] = 1
                    queue.append(i)
                    total += 1
        
        return total
                
    for i in range(1,n+1):
         if win(i) + lose(i) == n-1:
                answer += 1
        
    return answer