순위 (프로그래머스-그래프)(java)

문제 출처: https://programmers.co.kr/learn/courses/30/lessons/49191

코딩테스트 연습 - 순위

 

문제 설명 

int n: n명의 선수 존재

int[][] results: [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 같은 값이 들어 있고, [4,3]은 4선수가 3선수를 이겼다는 의미.

 

경기 결과엔 모순이 없고 -> 순위가 확정된 선수의 수를 계산하라 !

 

문제풀이

 [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 의 예제에서

 

4, 3, 1 선수가 2를 이겼고, 2가 5를 이겼으므로 4,3,1이 5를 이겼다고 갱신시켜줘야 순위를 계산하기 쉽다. 

이때 필요한 알고리즘은 플로이드 와샬이다 !

 

1. 인접행렬을 만들고 모든 값을 INF로 설정한다. INF는 아직 갈 수 없는 경로를 의미한다.

    INF는 만들 수 있는 최대값으로 설정한다.

   => 이때 Integer.MAX_VAULE()같은 함수로 만들면 덧셈해서 음수로 넘어갈 수 있으니 주의하자.

        여기선 n의 최대가 100명이므로 최대(INF)는 100으로 잡았다. 

2.  이기는 노드가 row, 지는 노드가 col이되어 1을 체크한다.

    ex) 4->3이면 (4,3)-(row,col)에 1을 체크한다.

3. 플로이드 와샬을 통해서 어떤 정점을 거쳐서 갈 수 있는 경로가 있는지 알 수 있다. (4->2, 2->5 이면 4->5)

    (원래 플로이드 와샬의 주사용은 주로 한노드에서 한노드로 갈 때 더 짧은 경로로 갈 수 있는지 모든 노드를 갱신함)

4. 갱신 후의 인접그래프에서 갈 수 있는 경로는 INF -> 몇 번 건치는지 로 바뀐다. 

5. 순위가 정해진 노드는 해당 노드의 행과 열을 합쳤을 때 자신의 노드를 제외한 값이 모두 차 있어야 한다.

   그래야 순위가 정해진 노드이다. 

 

소스코드

package programmers;

import java.util.Arrays;

public class 순위 {
	public int solution(int n, int[][] results) {
		int answer = 0;
		int INF = 100;
		int[][] matrix = new int[n][n];

		// 행렬에 값 넣기
		for (int[] arr : matrix) {
			Arrays.fill(arr, INF);
		}
		for (int[] arr : results) {
			matrix[arr[0] - 1][arr[1] - 1] = 1;
		}

		// 플로이드 와샬로 방문 -> 방문을 통해 정복할 수 있는 값들 채워넣기
		// ex) 2 -> 5를 통해 1,3,4 -> 5가 가능해짐
		for (int via = 0; via < n; via++) { // 거치는 노드(경로)
			for (int depart = 0; depart < n; depart++) { // 시작 노드
				for (int destin = 0; destin < n; destin++) { // 도착 노드
					if (matrix[depart][destin] > matrix[depart][via] + matrix[via][destin]) {
						matrix[depart][destin] = matrix[depart][via] + matrix[via][destin];
					}
				}
			}
		}

//		for (int i = 0; i < matrix.length; i++) {
//			for (int j = 0; j < matrix.length; j++) {
//				System.out.printf("%3d ", matrix[i][j]);
//			}
//			System.out.println();
//		}

		for (int row = 0; row < n; row++) {
			boolean check = true;
			for (int col = 0; col < n; col++) {
				if (row == col) {
					continue;
				}
				if (matrix[row][col] == INF && matrix[col][row] == INF) {
					check = false;
					break;
				}
			}
			if (check)
				answer++;
		}

		return answer;
	}

	public static void main(String[] args) {
		순위 s = new 순위();
		int[][] computers = { { 4, 3 }, { 4, 2 }, { 3, 2 }, { 1, 2 }, { 2, 5 } };
		int answer = s.solution(5, computers);
		System.out.println(answer);
	}
}

 

플로이드 와샬 전 Matrix상태

 

플로이드 와샬 알고리즘 적용 후 Matrix상태

 

4, 3, 1 가 2 를 이겼고, 2가 5를 이겼으므로 4,3,1이 5를 이겼다고 갱신한다. 근데 이때 두 번 거쳐서 이겼으므로 값은,2가 된다. 

 

현재 5는 콜럼기준으로 봤을때 나머지 숫자가 다 차 있어서 순위가 정해졌고, 다 졌으므로 꼴등이다.

2의 경우 콜럼기준으로 봤을때는

 1

100

 1

 1

100

 5번째와의 관계에서 순위가 정해지지 않은 것 같지만

로우기준으로 봤을 때는 100 100 100 100 1이므로 2가 5를 이긴 흔적이 남아있다.

따라서 2는 1과 3과 4한테 졌지만 5를 이겼으므로 4등이 되어 순위가 정해진다.

 

따라서 row와 colunm줄을  다 따져서 자신의 노드 인덱스를 제외한 값이 차있어야 순위가 정해진 것이다. 그것을 확인하면 된다. 

 

 

까다로웠던 테케:

[[3, 5], [4, 2], [4, 5], [5, 1], [5, 2]]