문제 설명:
n명의 권투선수가 권투 대회에 참여했고 각각 1번부터 n번까지 번호를 받았습니다. 권투 경기는 1대1 방식으로 진행이 되고, 만약 A 선수가 B 선수보다 실력이 좋다면 A 선수는 B 선수를 항상 이깁니다. 심판은 주어진 경기 결과를 가지고 선수들의 순위를 매기려 합니다. 하지만 몇몇 경기 결과를 분실하여 정확하게 순위를 매길 수 없습니다. 선수의 수 n, 경기 결과를 담은 2차원 배열 results가 매개변수로 주어질 때 정확하게 순위를 매길 수 있는 선수의 수를 return 하도록 solution 함수를 작성해주세요.
제한사항
- 선수의 수는 1명 이상 100명 이하입니다.
- 경기 결과는 1개 이상 4,500개 이하입니다.
- results 배열 각 행 [A, B]는 A 선수가 B 선수를 이겼다는 의미입니다.
- 모든 경기 결과에는 모순이 없습니다.
입출력 예
2번 선수는 [1, 3, 4] 선수에게 패배했고 5번 선수에게 승리했기 때문에 4위입니다. 5번 선수는 4위인 2번 선수에게 패배했기 때문에 5위입니다.
풀이:
이 문제를 보고 각 노드 기준 부모와 자식 노드들을 다 구하려고 했다. 하지만 불가능하다.
테스트케이스 보러갔다가 힌트를 얻어버려서
바로 플로이드 워셜을 써보도록했다.
def solution(n, results):
graph =[[0] * (n) for _ in range(n)]
for i in results:
graph[i[0]-1][i[1]-1] = 1 # 승리표시
graph[i[1]-1][i[0]-1] = -1 # 패배표시
# 승, 패 그래프 업데이트 플로이드
for k in range(n): # via
for i in range(n): # start
for j in range(n): # end
if graph[i][k] == graph[k][j] == 1: # start > via, via > end, start > end
graph[i][j] = 1
# 패배한 경로도 표시해줌.
graph[j][i] = graph[j][k] = graph[k][i] = -1
res = 0
for line in graph:
if line.count(0) == 1:
res += 1
return res
print(solution(5, [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]]))
플로이드 - 워셜은 모든 노드로에 최단거리를 찾는 것이다.
모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구하는 알고리즘 인데 n^3 이라 가능할까 했는데 가능하다.
start > via 가 참이고, via 에서 end가 참이면 start 에서 end 도 참이다.
반대로 지는 경우도 반대 코드로 써주면 된다.
최신화된 graph 를 돌면서
각 라인에 0이 한개면 그 사람은 몇 등인지 알 수있다.
왜냐하면 1은 이긴사람이기 -1 은 진 사람이기때문에 누구한테 지고 이기고를 다 알기 때문이다.
댓글