[프로스래머스][Python] 순위 - 코팩

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

프로그래머스

문제

이 문제를 풀기 위해서 두 개의 그래프를 만들어줬다. 사람 A와 사람 B가 있을 때 A가 B를 이긴다고 하자. 한 그래프는 간선의 방향을 이기는 사람에서 지는 사람으로 가는 방향을 가진 그래프를, 다른 그래프는 반대의 방향을 가진 간선을 이용한 그래프를 만들어주었다. 이 두 그래프에서  한 노드에서 몇 개의 노드로 이동할 수 있는지 확인하여 개수가 자신을 제외한 모든 노드를 방문할 수 있다면 순위가 확실한 노드임을 알 수 있다.

 

이를 위해 BFS를 활용하여 문제를 풀어주었다.

from collections import deque
def bfs(s_c, n, graph):
    queue = deque([s_c])
    result = 0
    visited = [False for _ in range(n+1)]
    visited[s_c] = True
    while queue:
        c = queue.popleft()
        for n_c in graph[c]:
            if visited[n_c] == False:
                visited[n_c] = True
                queue.append(n_c)
                result += 1
    return result
    

def solution(n, results):
    answer = 0
    graph = [[] for _ in range(n+1)]
    rev_graph = [[] for _ in range(n+1)]
    for a,b in results:
        graph[a].append(b)
        rev_graph[b].append(a)
    for i in range(1, n+1):
        total = bfs(i, n, graph) + bfs(i, n, rev_graph)
        if total == n-1:
            answer += 1
    return answer