순위
문제 설명
n명의 권투선수가 권투 대회에 참여했고 각각 1번부터 n번까지 번호를 받았습니다. 권투 경기는 1대1 방식으로 진행이 되고, 만약 A 선수가 B 선수보다 실력이 좋다면 A 선수는 B 선수를 항상 이깁니다. 심판은 주어진 경기 결과를 가지고 선수들의 순위를 매기려 합니다. 하지만 몇몇 경기 결과를 분실하여 정확하게 순위를 매길 수 없습니다.
선수의 수 n, 경기 결과를 담은 2차원 배열 results가 매개변수로 주어질 때 정확하게 순위를 매길 수 있는 선수의 수를 return 하도록 solution 함수를 작성해주세요.
제한사항
- 선수의 수는 1명 이상 100명 이하입니다.
- 경기 결과는 1개 이상 4,500개 이하입니다.
- results 배열 각 행 [A, B]는 A 선수가 B 선수를 이겼다는 의미입니다.
- 모든 경기 결과에는 모순이 없습니다.
입출력 예
n results return 5 [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 2
입출력 예 설명
2번 선수는 [1, 3, 4] 선수에게 패배했고 5번 선수에게 승리했기 때문에 4위입니다.
5번 선수는 4위인 2번 선수에게 패배했기 때문에 5위입니다.
concept
- 구글링함. 이건 생각을 전혀전혀전혀전혀 하지 못하였다..
- 가장 많이 이긴 놈이 제일 쎈게 아니다..! 이긴수가 같더라도 상대한테 졌을 수도 있기 때문..
- 그래서 구글링함..
Code
def solution(n, results):
answer = 0
#정확하게...?
#가장 많이 이긴 놈이 제일 쎈게 아니다...
#이긴수가 비슷하더라도.. 상대 녀석에게 졌을 수 있기 때문..!
#그렇담 제일 많이 진 녀석으로 생각해도..?
graph = [ [0]*(n+1) for _ in range(n+1)]
for win, los in results:
graph[win][los] = -1
graph[los][win] = 1
#floyd warshall
for k in range(1,n+1):
for i in range(1,n+1):
for j in range(1,n+1):
#자기 자신을 제외하고 승패 여부를 알 수 없는 경우
if(i!=j and graph[i][j] == 0):
if (graph[i][k] == 1 and graph[k][j] == 1):
#삼단논법 마냥 가능하다면
graph[i][j] = 1
elif(graph[i][k] == -1 and graph[k][j] == -1):
graph[i][j] = -1
#승패를 확연하게 알 수 있는 것이 왜 이기고 지기고 모두 명확해야하는지 아직 이해하지 못함
for i in range(1,n+1):
if graph[i][1:].count(0) == 1:
answer+=1
return answer참고
- 지나가는 경로를 탐색
- 모든 경로의 최소비용을 구할 수 있음..
- 더 공부할 것..
hello