[프로그래머스] 순위 / 그래프 / python

문제

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

n명의 권투선수가 권투 대회에 참여했고 각각 1번부터 n번까지 번호를 받았습니다. 권투 경기는 1대1 방식으로 진행이 되고, 만약 A 선수가 B 선수보다 실력이 좋다면 A 선수는 B 선수를 항상 이깁니다. 심판은 주어진 경기 결과를 가지고 선수들의 순위를 매기려 합니다. 하지만 몇몇 경기 결과를 분실하여 정확하게 순위를 매길 수 없습니다.

선수의 수 n, 경기 결과를 담은 2차원 배열 results가 매개변수로 주어질 때 정확하게 순위를 매길 수 있는 선수의 수를 return 하도록 solution 함수를 작성해주세요.

제한사항

• 선수의 수는 1명 이상 100명 이하입니다.
• 경기 결과는 1개 이상 4,500개 이하입니다.
• results 배열 각 행 [A, B]는 A 선수가 B 선수를 이겼다는 의미입니다.
• 모든 경기 결과에는 모순이 없습니다.

풀이

아이디어

삼단 논법이 바로 떠오르는 문제이다

a>b이고, b>c이면 ⇒ a>c

1이 2를 이기고 2가 3을 이기면 1은 3을 이긴다

삼단 논법하면 떠오르는 알고리즘은 플루이드 와샬이다

플로이드 와샬(Floyd Warshall)

모든 노드로부터 다른 노드까지의 최단 거리를 찾는 알고리즘이다

i노드에서 j노드 까지 가는 최단 거리를 구할 때 i → j 바로 가는 것보다 i → k → j로 가는 것이 최단 거리인 경우가 있다

모든 경우를 찾아 최솟값을 찾는 알고리즘

1. 하나의 노드에서 다른 노드까지 바로 갈 수 있다면 : 최소 비용 저장
2. 갈 수 없는 경우 : INF저장
3. 3중 for문을 통해 거쳐가는 정점을 설정한다
   1. 해당 정점을 거쳐가서 비용이 줄어든다 → 최소비용으로 교체
4. 반복하면서 최단 경로를 탐색

#거쳐가는 정점
for k in range(n):
	#시작 정점
	for i in range(n):
		#도착 정점	
		for k in range(n):

플루이드 와샬을 이용한 풀이

i번째 사람의 순위는 2가지 방법으로 결정 할 수 있다

1. i번째 사람이 다른 사람과 n-1번 경기를 함
2. 이미 순위가 결정된 사람과 싸워 나온 승패를 이용

이는, 바로 알 수도 있고, 한다리 건너건너 알 수 도 있다는 것 ⇒ 플루이드 와샬을 이용한다

일반적인 경우 겨처가는 정점이 있을 때 비용이 더 적은지 확인 하는 절차가 필요하다

하지만 지금은 연결이 됐는지만 확인하면 됨

 

def solution(n, results):

    ranks = [[0] * (n) for _ in range(n)]
    
    for win, lose in results:
        ranks[win-1][lose-1] = 1
        ranks[lose-1][win-1] = -1

    for k in range(n):
        for i in range(n):
            for j in range(n):
                if i == j:  continue                # 대각선 방향 무시
                if ranks[i][j] != 0:   continue     # 이미 값이 들어있는 경우
                if ranks[i][k] == 1 and ranks[k][j] == 1:
                    ranks[i][j] = 1
                    ranks[j][i] =  -1
    answer = 0
    print(ranks)
    for per in ranks:
        if per.count(0) == 1:
            answer += 1
    return answer