[Java][programmers] 순위 문제풀이

※ 문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/49191

프로그래머스

 

1. 문제 설명

---

n명의 권투선수가 있고, 1:1로 진행되는 경기 결과의 일부분이 배열 형태로 주어진다.

이 때, 정확하게 순위를 매길 수 있는 선수의 수를 반환하도록 구현하는 문제이다.

2. 예시

---

입력이 아래와 같이 주어져 있다.

• n = 5
• result = [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] ([A, B]는 "A가 B를 이겼다" 는 의미)

경기 결과를 보기 쉽게 도식화 하면 아래와같다.(4 -> 3 표시는 4가 3을 이겼다는 뜻이며, [4, 3] 으로 나타내고 있음)

• 2번 선수는 1, 3, 4번에게 졌고 5번을 이겼기 때문에 4등이라는 것을 알 수 있다.
• 5번 선수는 4등인 2번 선수에게 졌기 때문에 5등이라는 것을 알 수 있다.

그래프를 보면, 4번은 2번을 이기고 2번은 5번을 이긱 때문에, 4번은 5번을 이긴다는 것을알 수 있다. 마찬가지로 3번은 2번을 이기고 2번은 5번을 이기기 때문에 3번은 5번을 이기는 것을 알 수 있다. 이런 식으로 실제로 입력으로 주어지지는 않았으나 간접적으로 승패를 알 수 있는 결과를 그래프에 모두 표시해 보면 아래와 같다.

2번과 5번 선수는 화살표가 들어오고 나가는 부분을 별도로 표시해 주었는데, 갯수가 전체 선수(n) -1 이다. 즉, 본인을 제외한 모든 선수(n-1명)와의 승패를 직/간접적으로 알 수 있기 때문에 순위도 알 수 있게 된다.

3. 문제 풀이

---

위 예시에서 본 것처럼 각각의 노드(선수)에 대해 다른 모든 노드들이 연결되는지 알기 위해 플로이드 와샬(Floyd-Warshall) 알고리즘을 응용하였다. 플로이드 와샬 알고리즘은 보통 가중치가 부여되지만, 본 문제에서는 연결이 된 경우를 True로, 연결되지 않은 경우를 False로 두어서 아래와 같이 A → B, B → C 일 때, A → C를 구할 수 있게 된다.

 

DP[A][C] = (DP[A][C] == true) || (DP[A][B] == true && DP[B][C] == true)

우선 문제를 풀기 위해 nXn 형태의 매트릭스에 주어진 입력값(승, 패 결과값)을 넣는다.

boolean[][] check = new boolean[n+1][n+1]; // 0번은 사용하지 않으며 1 ~ n번 노드 사용

// 입력으로 주어진 결과 배열에서, i번째 결과인 [a, b]에 대해, check[a][b] = true 로 설정
for(int i=0; i<results.length; i++){ 
	check[results[i][0]][results[i][1]] = true;
}

위에서 주어진 예시를 사용해 check 배열을 채우면 다음과 같다.

다음, 플로이드 와샬 알고리즘을 활용해 간접적으로 알 수 있는 결과도 모두 채워보자.

※ 플로이드 와샬 알고리즘의 디테일한 동작 과정은 플로이드 와샬 이해하기(https://uldada.tistory.com/16) 참조

for(int k=1; k<n+1; k++){
	for(int i=1; i<n+1; i++){
		for(int j=1; j<n+1; j++){
        		// check[i][j] 가 채워지지 않은 경우, check[i][k] 와 check[k][j]가 True인지 확인
			if(!check[i][j] && check[i][k] && check[k][j]){ 
				check[i][j] = true;
			}
		}
	}
}

코드를 수행한 결과, 다음과 같은 매트릭스를 얻을 수 있다.

여기서 i번 행은 i가 이길수 있는 대상을, i번 열은 i를 이길수 있는 대상을 의미한다. 즉, i번 행과 i번 열의 T값의 합이 4가 되어야 한다(n-1이 되어야 함). 코드를 보면 아래와 같다.

int answer = 0; // 순위를 알 수 있는 선수 명 수
int[] count = new int[n+1]; // 각 번호 당 True 총 개수를 넣을 변수

for(int i=1; i<n+1; i++){
	for(int j=1; j<n+1; j++){
		if(check[i][j]){
			count[i]++;
			count[j]++;
		}
	}
}
        
for(int i=1; i<n+1; i++){
	if(count[i] == n-1){
		answer++;
	}
}

그리고 그 결과 아래와 같이 2번, 5번이 충족하는 것을 확인할 수 있다.

최종적으로 전체 코드는 다음과 같다.

class Solution {
    public int solution(int n, int[][] results) {
        int answer = 0;
        boolean[][] check = new boolean[n+1][n+1];
        int[] count = new int[n+1];
        for(int i=0; i<results.length; i++){
            check[results[i][0]][results[i][1]] = true;
        }
        
        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(!check[i][j] && check[i][k] && check[k][j]){
                        check[i][j] = true;
                    }
                }
            }
        }
        
        for(int i=1; i<n+1; i++){
            for(int j=1; j<n+1; j++){
                if(check[i][j]){
                    count[i]++;
                    count[j]++;
                }
            }
        }
        
        for(int i=1; i<n+1; i++){
            if(count[i] == n-1){
                answer++;
            }
        }
        
        return answer;
    }
}