[프로그래머스] 순위 - 파이썬/그래프

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

1차 풀이

def dfs(graph,x,visited):

    visited[x] = True

    for i in graph[x]:
        if not visited[i]:
            dfs(graph,i,visited)

    return visited


def solution(n, results):

    answer = 0

    win = [ [] for _ in range(n+1) ]
    lose = [ [] for _ in range(n+1) ]
    real_win  = [ [] for _ in range(n+1) ]
    real_lose  = [ [] for _ in range(n+1) ]

    for i in results:
        win[i[0]].append(i[1])
        lose[i[1]].append(i[0])

    for i in win:
        i.sort()
    for i in lose:
        i.sort()
    #
    # print(win)
    # print(lose)

    for i in range(1,n+1):
        real_lose[i] = lose[i]
        for j in lose[i]:
            real_lose[i] += lose[j]
        real_lose[i] = list(set(real_lose[i]))

    # print(real_lose)

    for i in range(1,n+1):
        visited = [ [] for _ in range(n+1) ]
        dfs(win,i,visited)
        for j in range(1,len(visited)):
            if visited[j]:
                real_win[i].append(j)

    print(real_win)
    ans  = [ [] for _ in range(n+1) ]
    for i in range(n+1):
        ans[i] = real_win[i]+real_lose[i]
        if len(ans[i]) == n:
            answer+=1

    # print(ans)
    #
    # print(answer)

    return answer

시간초과가 발생했다.

검색해보니 플루이드-와샬 알고리즘을 통해 푸는 문제였다.

2차 풀이

def solution(n, results):
    answer = 0
    graph=[[0 for _ in range(n+1)] for _ in range(n+1)]
    for a, b in results:
        graph[a][b]=1
    for k in range(1, n+1):
        for i in range(1, n+1):
            for j in range(1, n+1):
                if graph[i][j]==1 or (graph[i][k]==1 and graph[k][j]==1):
                    graph[i][j]=1
    answers=[0 for _ in range(n+1)]
    for i in range(1, n+1):
        for j in range(1, n+1):
            if graph[i][j]==1:
                answers[i]+=1
                answers[j]+=1
    for i in range(1, n+1):
        if answers[i]==n-1:
            answer+=1
    return answer