순위

문제 링크 : 코딩테스트 연습 - 순위 | 프로그래머스 (programmers.co.kr)

코딩테스트 연습 - 순위

 

플로이드 와샬을 이용한 문제이다.

2차원 배열 bool res[101][101]; 을 선언하여 다음과 같이 정의할 수 있다.

 

• res[x][y] = true : x가 승리하고 y가 패배한 경우 
• res[x][y] = false : x가 승리하고 y가 패배했는지 알 수 없는 경우

 

res[x][y] = true 일 경우, 다음과 같이 그래프를 설계한다고 가정해본다.

 

그렇다면, 문제에 주어진 input 을 다음과 같이 그래프를 설계할 수 있다.

 

 

이제 해야할 작업은 선수들 간의 승리와 패배를 결정하는 작업을 진행해야 한다.

예를 들어 5번 선수를 보도록 한다.

현재 알 수 있는 정보는 res[2][5] = true 인데, 그래프를 보면 다음과 같은 정보를 얻을 수 있다.

 

res[1][5] = true, res[3][5] = true, res[4][5] = true

 

확실한 것은 이러한 정보는 res[2][5] 로부터 시작되어 얻을 수 있다는 정보이다.

플로이드 와샬 알고리즘을 생각해본다면, O( \(N^{3}\) ) 으로 특정 지점 a 에서 특정 지점 b 으로의 최단 경로를 알 수 있다.

이러한 알고리즘을 활용하여 다른 선수들과의 승리와 패배를 결정하는데 도움이 된다.

아래와 같은 식을 통해 선수들과의 승리와 패배를 결정할 수 있다.

 

res[x][y] = res[x][y] | (res[x][t] && res[t][y])

   

중간에 or 연산자가 있는 것은 한번 true 로 마킹되었을때 계속해서 true 를 유지하기 위함이다.

x 번째 선수와 y 번째 선수 사이에 t 번째 선수가 있다고 가정해보자.

 

 

여기서 x 선수가 승리하고 y 선수가 패배한 것을 위 그래프를 통해 직관적으로 알 수 있다.

위에서 언급한 식을 통해서 x 선수가 승리하고 y 선수가 패배한 것을 다음과 같이 알아낼 수 있다.

 

res[x][y] = (false) | (true && true) = (false) | (true) = true

 

따라서 그래프는 다음과 같이 변경되는 것을 알 수 있다.

 

 

이를 코드화한다면 다음과 같이 모든 선수들간의 승리와 패배를 결정할 수 있다.

 

for (int k = 1; k <= n; k++)
{
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			res[i][j] |= res[i][k] && res[k][j];
		}
	}
}

 

모든 선수들간의 승리와 패배를 결정하였다.

그렇다면 특정 선수의 순위를 매길 수 있는지를 알 수 있으려면 특정 선수와 다른 선수들과의 승리와 패배가 결정된 경우일 때이다.

즉, (N - 1) 만큼의 선수와 특정 선수가 승리와 패배가 결정되었을때 순위를 매길 수 있으므로 이 경우에 카운팅하면 된다.

 

 

#include <string>
#include <vector>

using namespace std;

// res[x][y] = true <= x 번째 선수가 y 번째 선수를 이겼다!
bool res[101][101];

int solution(int n, vector<vector<int>> results) {
	int answer = 0;

	for (int i = 0; i < results.size(); i++)
	{
		res[results[i][0]][results[i][1]] = true;
	}

	for (int k = 1; k <= n; k++)
	{
		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j <= n; j++)
			{
				res[i][j] |= res[i][k] && res[k][j];
			}
		}
	}

	for (int i = 1; i <= n; i++)
	{
		int cnt = 0;
		for (int j = 1; j <= n; j++)
		{
			if (res[i][j] || res[j][i]) cnt++;
		}
		if (cnt == n - 1)
			answer++;
	}

	return answer;
}