[java] 프로그래머스 - 순위

문제

프로그래머스-순위
주어진 경기 결과를 가지고 정확하게 순위를 매길 수 있는 선수의 수를 구하는 문제

• 제한 사항
  선수의 수 n : 1 <= n <= 100
  경기 결과 results의 각 행 [A, B] => ‘A 선수가 B 선수를 이겼다’
  경기 결과의 수 results.length() : 1개 이상 4,500 이하
  모든 경기 결과에는 모순이 없다

• 예시
  n = 5
  results = [[4,3], [4,2], [3,2], [1,2], [2,5]]
  2번선수는 [1,3,4] 선수에게 패배했고, 5번선수에게 승리했기때문에 4위다
  5번선수는 4위인 2번선수에게 패배했기때문에 5위이다
  순위를 알 수 있는 선수는 [2,5]이다

풀이

우선 방향성이 있는 그래프이므로 방향을 따라 어디까지 도달가능한 지 확인해야한다
예를들어 [A] <- [C]일때 A와의 경기에서 C가 패배했다고 한다면, 위의 예시의 경기 결과 일부에서 [1,3,4] <- [2] <- [5]이다
[5]에서 [2]를 거쳐서 [1,3,4]로 갈 수 있다는 것은, [5]가 [1,2,3,4]와 경기에서 패배했다는 뜻이다

그림 1: 경기결과(results)를 토대로 경기내용을 기록한다
그림 2: bfs로 <-를 타고 이동할 수 있는(경기에서 패배) 모든 선수를 찾는다
그림 3: 노랑색 칸은 1이 패배한 선수들, 초록색 칸은 1이 승리한 선수들을 의미한다

bfs후 생성된 그림 3을 토대로 승리 수 + 패배 수가 n-1(자신제외)면 순위를 알 수 있음을 의미한다

소스코드

import java.util.*;
class Solution {
public int solution(int n, int[][] results) {
		int answer = 0;
		boolean chk[][] = new boolean[n + 1][n + 1];
		for (int i = 0; i < results.length; i++) {
			chk[results[i][1]][results[i][0]] = true; // 그림 1을 채움
		}
		Queue<Integer> q = new LinkedList<>();
		for (int i = 1; i < n + 1; i++) {
			q.clear();
			q.add(i);
			chk[i][i] = false;
			boolean[] visit = new boolean[n + 1];
			while (!q.isEmpty()) {
				int curr = q.poll();
				for (int j = 1; j < chk.length; j++) {
					if (chk[curr][j] && !visit[j]) {
						chk[i][j] = true;
						visit[j] = true;
						q.add(j);
					}
				}
			}
		}
		int[] ans = new int[n + 1];
		for (int i = 1; i < ans.length; i++) {
			for (int j = 1; j < ans.length; j++) {
				ans[i] += chk[i][j] ? 1 : 0; // 승리 수와 패배 수를 더함
				ans[j] += chk[i][j] ? 1 : 0;
			}
		}
		for (int i = 1; i < ans.length; i++) {
			if (ans[i] == n - 1)
				answer++;
		}
		return answer;
	}
}