[level3] 프로그래머스 - 순위(JAVA)

 

 

[ 풀이 방법 ]

- n행, n열인 배열을 만들어서 진 경우는 -1, 이긴 경우는 1로 초기화 해준다.

 

 

- 이 문제를 풀때, 플로이드 와샬의 개념을 적용하였다.

모든 정점에서 모든 정점까지의 최단거리
거쳐가는 정점을 기준으로 최단거리를 구해야 한다는 것이다!!

  i -> k이고 k -> j 라면, i -> j임을 활용한다.
  즉, matrix[i][k]와 matrix[k][j]가 지든 이기든 같은 경우이면, matrix[i][j]와도 결과가 같음을 이용한다.

 

 

- 아직 0으로 남아있는 곳은 찾아갈 수 없으므로,
   자신에서 자신으로 가는 경우가 아닌데, 0이라면 순위를 알 수 없는 경우이다.

 

 

 

 

[ 전체 코드 ]

class Solution {
    public int solution(int n, int[][] results) {
       	int answer = 0;

		int[][] matrix = new int[n][n];
		for (int i = 0; i < results.length; i++) {
			int win = results[i][0] - 1;
			int lose = results[i][1] - 1;
			matrix[win][lose] = 1;
			matrix[lose][win] = -1;
		}

		for (int k = 0; k < n; k++) {
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					if (i == j || matrix[i][j] != 0)
						continue;
					if (matrix[i][k] == matrix[k][j])
						matrix[i][j] = matrix[i][k];
				}
			}
		}

		for (int i = 0; i < n; i++) {
			boolean isOk = true;
			for (int j = 0; j < n && isOk; j++)
				if (i != j && matrix[i][j] == 0)
					isOk = false;

			if (isOk)
				answer++;
		}

		return answer;
	}
}