[최단거리] 순위

문제

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

프로그래머스

솔루션

• 특정 선수가 어떤 선수를 이겼는지 알기 위해선 그 선수와 관련 된 모든 경우를 찾아봐야함.
• 플루이드 워셜 알고리즘은 최단거리를 구하는 알고리즘이지만 어떤 노드(모든)에서부터 다른 모든 노드까지의 경우의 수를 다 구할 수 있음. 이 점을 활용해서 문제를 풀어본다.
• 예를 들어 1>2>3>4 일 때, 1번이 4번을 확실히 알기 위해선 (1,3) (3,4)를 통해 알 수 있음.
• 이것을 코드화 하면 아래와 같음

for k in range(1, n+1):
        for i in range(1, n+1):
            for j in range(1, n+1):
                if gr[i][j] == 0 and gr[i][k] and gr[k][j]:
                    gr[i][j] = 1

• 이후 해당 선수의 순위가 정확히 판단 가능한지는 col_sum[i]+row_sum[i] == (n-1) 인 경우로 알 수 있음

코드

# result[a,b] : a는 b를 이겼다
def solution(n, results):
    answer = 0  # 정확하게 순위를 매길 수 있는 선수의 수
    gr = [[0]*(n+1) for i in range(n+1)]
    for winner, loser in results:
        gr[winner][loser] = 1

    for k in range(1, n+1):
        for i in range(1, n+1):
            for j in range(1, n+1):
                if gr[i][j] == 0 and gr[i][k] and gr[k][j]:
                    gr[i][j] = 1
    col_sum = [0]*(n+1)
    row_sum = [0]*(n+1)

    for i in range(1, n+1):
        for j in range(1, n+1):
            col_sum[j] += gr[i][j]
            row_sum[i] += gr[i][j]

    for i in range(n+1):
        if (col_sum[i]+row_sum[i] == (n-1)):
            answer += 1
    return answer


print(solution(5,	[[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]]))