GAME

https://algospot.com/judge/problem/read/GAME

현재 숫자에서 가장 작은 값을 가진 인덱스를 찾음.

MAP에 모든 값을 저장하고 탐색하여 가장 작은 값을 조건에 맞춰 얻음.

그리디 알고리즘의 시간복잡도는 O(n^2)와 같다.

#include 
int STACK[501];
int SP;
int MAP[501][501];
int K, N;
bool Check(int _num)
{
	SP = 0;
	int _index = 0,_value = 999;
	for (int i = 0; i < N; i++)
	if (MAP[i][0] != -1 && _value > MAP[i][_num]){
		_value = MAP[i][_num];
		_index = i;
	}

	for (int i = 0; i < N; i++)
	if (MAP[i][0] != -1 && MAP[_index][_num] == MAP[i][_num])
		STACK[SP++] = i;

	if (SP > 1){
		for (int i = 0; i < SP; i++)
			printf("%d%c", STACK[i]+1, (i == SP - 1) ? '\n' : ' ');

		return false;
	}
	else
		MAP[STACK[0]][0] = -1;
	return true;
}
int main()
{
	int T;
	for (scanf("%d", &T); T > 0; T--)
	{
		/* Input */
		scanf("%d %d", &N, &K);
		for (int i = 0; i < N; i++)
		for (int j = 0; j < K; j++)
			scanf("%d", &MAP[i][j]);
		/* Solution */
		bool E = false;
		for (int i = 0; i < K;i++)
		if (!Check(i))
		{
			E = true;
			break;
		}
		if (!E && K < N)
		{
			SP = 0;
			for (int i = 0; i < N;i++)
				if (MAP[i][0] != -1)
					STACK[SP++] = i;

			for (int i = 0; i < SP; i++)
				printf("%d%c", STACK[i]+1, (i == SP - 1) ? '\n' : ' ');
		}
	}
	return 0;
}