문제 링크 https://programmers.co.kr/learn/courses/30/lessons/49191 코딩테스트 연습 - 순위 5 [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 2 programmers.co.kr 풀이 과정 필자는 이 문제를 보고 순서대로 로직을 정리해봤다. 1. 선수별 경기 결과를 인접행렬에 저장한다. 선수 1이 선수 2를 이긴 경우, graph[1][2] = 1, 선수 2가 선수 1에게 졌으니 graph[2][1] = 0이 들어간다. 2. 주어진 경기 결과로 구현한 인접행렬을 바탕으로 확정된 순위를 구한다. 선수가 N명일 때, 선수a가 지고, 이긴 경우를 합쳐 N-1인 경우 해당 선수의 순위를 확정지을 수 있다. ex) 선수 2의 경우, 이긴 경기..

플로이드-워셜 알고리즘 그래프에서, 한 정점에서 다른 정점으로 가는 최단거리가 있다. 플로이드-워셜 알고리즘을 사용한다면 각각의 모든 정점에서 모든 정점으로 가는 최단거리를 전부 구할 수 있다. 즉, 1 ~ 2, 1 ~ 3, 1 ~ N 2 ~ N 3 ~ N 4 ~ N 5 ~ N 모든 경로에서 전부 최단 거리를 구할 수 있다. 2 -> 1로 가는 최단 경로를 볼 때, 2 -> 1은 9 2 -> 3 -> 1은 7로 노드 3을 거쳐가는 것이 더 빠름 이렇게 노드를 거쳐서 가는게 더 빠른 경로까지도 플루이드-워셜 알고리즘을 통해 구할 수 있다는 것이다. 플로이드-워셜 알고리즘은 DP(Dynamic Programming) 기법을 사용한 알고리즘이다. 즉, 노드 0개를 거쳐가는 최단거리를 구하고, 노드 1개, 노드..