[프로그래머스 level_3] 순위 for JAVA

https://programmers.co.kr/learn/courses/30/lessons/49191

프로그래머스

[문제 설명]

 

n명의 권투선수가 권투 대회에 참여했고 각각 1번부터 n번까지 번호를 받았습니다. 권투 경기는 1대1 방식으로 진행이 되고, 만약 A 선수가 B 선수보다 실력이 좋다면 A 선수는 B 선수를 항상 이깁니다. 심판은 주어진 경기 결과를 가지고 선수들의 순위를 매기려 합니다. 하지만 몇몇 경기 결과를 분실하여 정확하게 순위를 매길 수 없습니다.

선수의 수 n, 경기 결과를 담은 2차원 배열 results가 매개변수로 주어질 때 정확하게 순위를 매길 수 있는 선수의 수를 return 하도록 solution 함수를 작성해주세요.

 

제한사항

• 선수의 수는 1명 이상 100명 이하입니다.
• 경기 결과는 1개 이상 4,500개 이하입니다.
• results 배열 각 행 [A, B]는 A 선수가 B 선수를 이겼다는 의미입니다.
• 모든 경기 결과에는 모순이 없습니다.

입출력 예

n	results	return
5	[[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]]	2

입출력 예 설명

2번 선수는 [1, 3, 4] 선수에게 패배했고 5번 선수에게 승리했기 때문에 4위입니다.
5번 선수는 4위인 2번 선수에게 패배했기 때문에 5위입니다.

 

[풀이]

플로이드워샬 알고리즘을 사용해서 문제를 해결했다. 해당 문제의 풀이 조건은 어떤 노드가 있을 때 그 노드의 입, 출 노드의 간선 수가 n-1이어야 한다는 것이다. 뿐만 아니라 만약 하나의 입력만 있다 하더라도 그 입력을 준 노드에 다른 모든 노드가 입력된다면 하나의 입력만 있더라도 순위를 알 수 있다.

플로이드워샬 알고리즘은 https://tosuccess.tistory.com/46에 정리해 놨다. 

 

일단 어떤 한 정점에 대해,  다른 정점과 비교해서 순위를 따질 수 있어야 한다.

1차원적으로 바로 알 수 있는 답안은 모든 정점이 자기 자신을 바라보거나(모두 졌거나) 1자 형태(a->b->c)로 존재하는 것인데, 문제는 그렇게 나오질 않는다.

 

그래서 조금 더 깊게 고민해봤다.

 

"한 정점의 순위를 따지려면 어떻게 해야 할까"

 

그러려면 특정 정점에 순위 상 앞쪽인 정점과 뒤쪽인 정점을 구별할 수 있어야 한다.

 

"그럼 그건 또 어떻게 해야 할까" 

 

해당 정점에 들어오는 진입차수와 진출차수의 개수를 알면 가능할 것이다.

 

"근데 예제에서 5에 해당하는 케이스는 순위를 예측할 수 있지만 진입차수는 한 개, 진출차수는 0개인데?"

 

가만 보면 예제에서 5가 가지고 있는 진입차수와 연결돼있는 2는 모든 정점과 연결되어있다.

 

여기서 힌트를 얻을 수 있다.

 

해당 정점으로 도착할 수 정점의 수. 즉, 해당 정점의 순위.

 

그리고 해당 정점에서 출발할 수 있는 정점의 수, 해당 정점 이후의 순위.

 

도착할 수 있는 정점의 수와 출발할 수 있는 정점의 수를 더한 개수가 전체 정점의 개수 - 1(본인)이면 해당 정점은 순위를 파악할 수 있게 된다.

 

정점 간 최단거리를 구하는 플로이드 워샬로 각 정점의 최단거리를 구하는 척하면서 연결이 되어있나 안되어있나 확인하는 방법을 사용한다.(말이 이상하다)

 

 

 

[코드]

package level3;

import java.util.Arrays;

public class Ranking {
	/**
	 * level 3
	 * 순위
	 * https://programmers.co.kr/learn/courses/30/lessons/49191
	 */
	public int solution(int n, int[][] results) {
		//모든 정점에서 갈 수 있으면, 그 정점은 비교 가능 대상이 됨.
		//플로이드 워샬로 최단거리표를 만들고, 표 중 [i][j], [j][i] 중 하나라도 길이 있으면 모든 정점에서 갈 수 있다고 판단.
		int INF = 100001;
		int answer = 0;
		int[][] fw = new int[n+1][n+1];
		
		//모든 경로 INF로 채우기
		for(int[] arr : fw) {
			Arrays.fill(arr, INF);
		}
		
		//플로이드 워샬 표 채우기
		for(int[] arr : results) {
			fw[arr[0]][arr[1]] = 1;
		}
		
		for(int k = 1; k < fw.length; k++) {				//거치는 경로
			for(int i = 1; i < fw.length; i++) {			//시작 정점
				for(int j = 1; j < fw.length; j++) {		//도착 정점 ex) k-1, i-2, j-3 이면 2->3 > 2->1->3을 비교
					if(fw[i][j] > fw[i][k] + fw[k][j]) {
						fw[i][j] = fw[i][k] + fw[k][j];
					}
				}
			}
		}
		
		for(int i = 1; i < fw.length; i++) {
			boolean flag = true;
			for(int j = 1; j < fw[i].length; j++) {
				if(i == j) continue;
				if(fw[i][j] == INF && fw[j][i] == INF) {
					flag = false;
					break;
				}
			}
			if(flag) answer++;								//모든 정점에서 갈 수 있는 정점을 찾은 경우
		}
		return answer;
	}
	
}

프로그래머스 테스트 케이스 통과

 

 

느낀 점 : 요즘 level 3을 보면서 한계를 많이 느낀다. 오늘 푼 문제도 사실 몇 번 고민하다가 해결방법이 떠오르지 않아 자료를 찾아봤고, 플로이드 워샬이라는 알고리즘을 사용해야 한다는 것을 알게 되었다. 먼저 플로이드워샬이라는 알고리즘을 공부하고 문제를 해결했다. 사실 이 문제에서는 플로이드워샬의 특징인 모든 정점에서 모든 정점까지 최단거리를 얻는다기 보다는 모든 정점에서 모든 정점까지 연결이 되어있나라는 특징을 위주로 사용하지 않았나 생각이 든다.

 

 

1년이 지난 지금 다시 문제를 풀어봤다. 솔직히 말하면 플로이드 워샬을 사용할 방법을 생각해 내진 못했다. 1년이 지나도 또다시 힌트를 얻어서 문제를 푸는 이유에 대해 깊게 고민해봤는데, 저 당시에 이 문제를 풀고 다시 풀어봤어야 했는데 안 풀고 지나간 게 원인이라고 생각이 들었다. 그래서 이번에는 조금 깊게 생각하고 문제의 의도를 파악하려고 노력했다.

 

**피드백은 언제나 환영입니다!