문제
링크 : https://school.programmers.co.kr/learn/courses/30/lessons/49191
사용 언어 : JAVA
내 생각
초기 생각
처음에는 Topology Sort를 활용한 문제인 줄 알았는데 아무리 생각해도 정렬을 하고서 어떻게 순위를 계산할 방법이 떠오르지 않았다... 결국 구글 신의 도움을 받고, "플로이드 와샬"을 활용해야 한다는 것을 알게되었다.
적용
어떻게 플로이드 와샬을 사용할 수 있을까?
일단 2차원의 인접 배열을 만든다. 그리고 가중치를 세가지를 사용할 것인데, 각각 1, 0, -1이다. (사실 값은 중요하지 않고 세가지 상태를 나타낼 수 있으면 된다)
array[A][B] == ?
- 1: A가 B를 이긴다
- 0: 알 수 없다.
- -1: A가 B에게 진다.
A와 C가 있는데, 이 둘 사이의 승패를 알 수 없다고 해보자. 그런데 만약 A가 B에게 이긴 적이 있고, C가 B에게 진 적이 있다면 겨뤄보지 않아도 A와 C의 승패를 유추할 수 있다. 이걸 간단하게 나타내면 아래처럼 될 것이다.
if(array[A][B]==1 && array[B][C]==1)
array[A][C]==1;플로이드 와샬은 쉽게 말해 모든 노드에 대해, 이 노드를 경유하였을 때 cost가 단축되는 루트를 찾아내 갱신하는 것이다. 이 문제의 경우는 이 선수(C)와는 겨뤄본 적 없지만, 나보다 약한 선수(B)의 전적을 참고해보니 이 선수(B)보다 더 약하군 내가 이길 수 있겠다, 를 유추하는 과정이다.
그렇게 비교를 다 마쳤을 때, 나와 싸웠을 때 승패를 알 수 없는 선수(array[나][X]==0)가 아무도 없을 때 나의 최종 순위를 정확하게 예측할 수 있다.
최종 코드
더보기
class Solution {
public int solution(int n, int[][] results) {
int answer = 0;
// results를 2차원 배열로 변경
// map[A][B] = 1 | -1 | 0
// 1: A가 B를 이김, -1: A가 B에게 짐, 0: 알 수 없음
int[][] map = new int[n][n];
for(int[] result: results) {
map[result[0]-1][result[1]-1] = 1;
map[result[1]-1][result[0]-1] = -1;
}
// 플로이드 와샬 시작
// step을 고려했을 때 start->end가 바뀌는가?
for(int step=0; step<n; step++) {
for(int start=0; start<n; start++) {
if(step == start) continue;
for(int end=0; end<n; end++) {
if(start==end || step==end) continue;
// start가 step을 이기고 step가 end를 이긴다면
// 당연히 start도 end를 이길 수 있다.
if(map[start][step]==1 && map[step][end]==1) {
map[start][end] = 1;
map[end][start] = -1;
}
}
}
}
int cnt;
// 한 줄 씩 봤을 때
for(int[] line: map) {
cnt = 0;
// 승패를 알 수 있는 선수들의 수가 N-1(자신 제외 모두)라면 answer에 추가
for(int l: line)
cnt += (l==0? 0: 1);
if(cnt==n-1) answer++;
}
return answer;
}
}느낀점
- 플로이드 와샬을 이렇게 사용할 수도 있구나,,
