프로그래머스 Graph - 순위 (파이썬)

Graph - 순위

 

* 프로그래밍 주안점

1. 가독성

2. 성능

 

문제링크: https://programmers.co.kr/learn/courses/30/lessons/49191

 

설명 (요약)

선수의 수 n, 경기 결과를 담은 2차원 배열 results가 매개변수로 주어질 때 정확하게 순위를 매길 수 있는 선수의 수를 return 하도록 solution 함수를 작성해주세요. 제한사항 results 배열 각 행 [A, B]는 A 선수가 B 선수를 이겼다는 의미입니다. 예: n results 5 [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 결과: 2

 

풀이전략

• 모든 경우의 수에 대한 그래프가 있어야 한다.
• Start, End 가 없는 상태에서 모든 경우를 알아야 하기에 '플루이드워셜' 알고리즘을 적용
• 승패 그래프를 그렸을때 항목의 가로축, 세로축에 승패를 알수없는 항목이 하나도 없는 경우가 모든 승패를 아는 경우다.

 

고려사항

• 플루이드 워셜 그래프 만들기

 

코드

 

def solution(n, results):
    # 1. 그래프 만들기
    # 1.1. 자기자신 = None
    # 1.2. 간선정보 입력
    graph = [[0] * n for _ in range(n+1)]
    #for a in range(1, n+1):
    #    graph[a][a] = None
    for a, b in results:
        graph[a-1][b-1] = 1     # Win
        graph[b-1][a-1] = -1    # Lose;  0 = None
    
    # 플루이드 워셜
    for k in range(0, n):
        for a in range(0, n):
            for b in range(0, n):
                # if graph[a][k] == None or graph[k][b] == None:
                #     continue
                if graph[a][b] == 0:
                    if graph[a][k] == 1 and graph[k][b] == 1:
                        graph[a][b] = 1
                    elif graph[a][k] == -1 and graph[k][b] == -1:
                        graph[a][b] = -1
    
    answer = 0
    # 0(= None) 이 하나인 경우(자기자신)는 승패를 확실히 아는 경우
    for i in range(0, n):
        if graph[i].count(0) == 1:
            answer += 1

    return answer


solution(5, [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]])       # return 2

 

Github: https://github.com/oksk1111/algorithm_python/blob/main/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4_%EA%B7%B8%EB%9E%98%ED%94%84_%EC%88%9C%EC%9C%84.ipynb