1. 문제 링크 및 문제
https://school.programmers.co.kr/learn/courses/30/lessons/49191
2. 해결 방법 생각해보자 ...
플로이드 워셜 알고리즘을 통해, 사이에 잃어버린 기록을 찾아준다 ! 어떻게 !?
[4,3] == 4번 선수가 3번 선수를 이겼다.
[3,2] == 3번 선수가 2번 선수를 이겼다.
해당 과정을 통해 우리는 4번 선수가 2번 선수를 이겼다는 걸 바로 알 수 있다.[4][2] == true !
하지만 컴퓨터는 모른다!
플로이드 워셜 알고리즘은 모든 간선의 최단거리를 구할 수 있는 알고리즘이다.
어떻게 최단거리를 구하냐?
중간노드를 정하여, 모든 간선을
i -> 중간노드 -> j로 갈 수 있는 최단거리를 확인한다.
중간노드는 어떻게 정하냐?
3중 반복문을 통해 정한다.
k가 중간노드 이다. k가 3중 반복문의 첫번째에 있다는 걸 명심하고 플로이드 워셜을 적용하여야 한다.int[][] arr = new int[N][N]; for(int k=0;k<N;k++){ // 중간 노드를 정한다 for(int i=0;i<N;i++){ // 2중 반복문을 통한 arr[][] 탐색 for(int j=0;j<N;j++){ if(i==j) continue; arr[i][j] = Math.min(arr[i][k]+arr[k][j], arr[i][j]); } } }여기서 arr[i][j]의 모든 값들은 INF 로 초기화 해두고 들어가야 한다! min 값을 구해야 하므로, 0이면 앙대요.
INF 는 그럼 또 어떻게 구해요 ..? => 나올 수 있는 최장거리
다시 문제로 돌아와서, 이 알고리즘을 사용하여 4번 선수가 2번 선수를 이겼다는 걸 똑똑한 우리가 컴퓨터에게 알려주자.
알고 있는 값
- 4번 선수가 3번 선수 이김 :
arr[4][3] = true; - 3번 선수가 2번 선수 이김 :
arr[3][2] = true;
우리가 모르지만 구해야 하는 값
- 4번 선수가 2번 선수를 이김 :
arr[4][2] = true ;
플로이드 워셜 적용
중간노드가 3 임을 활용해서, 4에서 2로 갈 때
arr[4][3] == true && arr[3][2] == true 가 성립하므로, ( 4 -> 3 -> 2 )
arr[4][2] = true! 이다.
그럼 3번 선수가 2번 선수에게 졌다 는 arr[3][2] = flase! 이냐? 아니다.
true , false 는 두가지 상태만 나타낼 수 있지만,
우리는 이김,짐,모름 을 표현해야 하기 때문에 1,-1,0 으로 표현해줄 것이다.
그럼 애초에 설명도 그렇게 하셔야ㅈ.. 편의를 위해서 ㅎㅎ
여기서 끝이면 좋겠지만 문제의 조건은
정확하게 순위를 매길 수 있는 선수의 수를 return 이다.
정확하게 안다? == 모든 선수와의 경기 결과를 안다
따라서, 플로이드 워셜 알고리즘 적용 후, arr를 탐색하며
자신을 제외한 모든 선수와의 결과값이 1 이거나 -1 일 때, 정확하게 알고 있는 것 이므로 answer ++ 를 해준다.
3. 코드
import java.util.*;
import java.io.*;
class Solution {
static int[][] arr ;
public int solution(int n, int[][] results) {
int answer = 0;
arr = new int[n+1][n+1];
int win,lose;
for(int i=0;i<results.length;i++){
win = results[i][0];
lose = results[i][1];
arr[win][lose] = 1; // 이겼당
arr[lose][win] = -1; // 졌당
}
// <-- 값 입력받기
// 플로이드 워셜
for(int k=1;k<n+1;k++){
for(int i=1;i<n+1;i++){
for(int j=1;j<n+1;j++){
if(i==j || k==i) continue ;
if(arr[i][j]==0 && arr[i][k] == 1 && arr[k][j] == 1){
// i가 k를 이김, k가 j를 이김 => i가 j를 이겼다! , 동시에 j는 i에게 졌다!
arr[i][j] = 1 ;
arr[j][i] = -1 ;
}
if(arr[i][j]==0 && arr[i][k]==-1 && arr[k][j]== -1){
// i가 k에게 짐, k가 j에게 짐 => i가 j에게 졌다! , 동시에 j가 i를 이겼다!
arr[i][j] = -1;
arr[j][i] = 1 ;
}
}
}
}
// <-- 플로이드 워셜 적용 끝
// 등수를 알고 있는 지 확인
for(int i=1;i<n+1;i++){
boolean check = true;
for(int j=1;j<n+1;j++){
if(i==j)continue;
if(arr[i][j] == 0){
check = false;
break;
}
}
if(check) answer ++ ;
}
return answer;
}
}테스트 결과값에 따른 arr 변화도 함께 첨부한당
