[프로그래머스] 순위

링크

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

프로그래머스

풀이

 

선수의 수 n, 경기 결과를 담은 2차원 배열 results가 매개변수로 주어질 때 정확하게 순위를 매길 수 있는 선수의 수를 구하는 문제이다.

 

 

먼저 선수간의 승패로 방향 그래프 2개를 만들 었습니다.

 

첫 번째 그래프는 내가 이긴 사람으로 향하는 그래프,

두 번재 그래프는 내가 진 사람으로 향하는 그래프,

 

그리고 문제에서는 선수의 수가 100이하 이기 때문에 그래프에서 최단 거리를 구하는 알고리즘 중에서

o(n^3)에 해당하는 플로이드 워셜을 이용하였습니다.

 

첫 번째 그래프에 플로이드 워셜을 이용하면 내가 이길수 있는 모든 선수가 구해지게 되고

 

두 번째 그래프에 플로이드 워셜을 이용하면 내가 질 수 있는 모든 선수가 구해지게 됩니다.

 

그리고 첫 번째 그래프와 두 번째 그래프를 모두 탐색하여 두개의 그래프중

A -> B 경우 즉 이기거나 지는 경우가 있을 경우에는 A 와 B는 서로 비교를 할 수 있다고 체크하고

 

A에서 모든 경우에 경로가 있다면 순위를 매길 수 있다고 하였습니다.

 

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<string>
#include<set>
#include<map>
#include<cstring>
#include<cmath>

#define SIZE 110
const int INF = 2e6;
using namespace std;

typedef long long int ll;

int arr[SIZE][SIZE];

void init() {
	for (int i = 0; i < SIZE; i++) {
		for (int j = 0; j < SIZE; j++) {
			if (i == j) continue;
			arr[i][j] = INF;
		}
	}
}

int solution(int n, vector<vector<int>> results) {
	
	init();

	for (auto result : results) {
		arr[result[0]][result[1]] = 1;
		arr[result[1]][result[0]] = 1;
	}


	int results_size = results.size();
	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (i == j) continue;

				arr[i][j] = min(arr[i][j], arr[i][k] + arr[k][j]);
			}
		}
	}

	int res = 0;
	for (int i = 1; i <= n; i++) {
		int cnt = 0;
		for (int j = 1; j <= n; j++) {
			if (i == j) continue;
			if (arr[i][j] != INF)
				cnt++;
		}

		res = cnt == n-1 ? res + 1 : res;
	}

	return res;
}