<사고력 훈련 문제 #5>: 행렬의 안장점 찾기

# 행렬의 안장점의 존재 여부와 그 위치, 값을 구하는 문제

---

 문제) $m*n$ 행렬에서 어떤 원소 $a[i][j]$가 $i$행에서 가장 작은 값이고 $j$열에서 가장 큰 값일 때, 이 행렬은 안장점(saddle point)을 갖는다고 말한다. 안장점이 존재한다고 할 때 이 안장점의 위치를 결정하는 C함수를 작성하라. 작성한 함수의 연산 시간은 얼마인가?

# 풀이

---

문제에서는 행렬의 안장점(saddle point)이 존재한다고 가정했지만, 직접 프로그래밍을 할 때는 예외상황에 대한 처리 또한 해주는 것이 좋다. 안장점(saddle point)이 있다면 어디 위치의 무슨 값이고, 만약 없다면 존재하지 않는다고 출력할 수 있는 프로그램을 작성해보자.

 안장점(saddle point)은 행에서 가장 작고, 열에서 가장 큰 값이므로 이 순서대로 문제 해결에 접근하자.  행에서 가장 작은 값을 얻고, 그 값이 열에서 가장 큰 지를 비교하면 된다. 그 행에 모든 열을 비교해야 하므로, 열을 고정한 후 모든 행을 살펴보는 방법을 택하면 된다. 이 부분만 신경쓴다면 크게 어려운 문제는 아니다.

/*************************************************
 ** 행렬의 안장점(saddle point) 구하기
*************************************************/

#include 
#include 
#include 

#define M_SIZE 10
#define N_SIZE 10

int arr[M_SIZE][N_SIZE];
//= {
//	{ 1,2,9,4,5,6,7,8,3,0 },
//	{ 1,2,3,4,5,6,7,9,8,0 },
//	{ 1,2,3,4,5,6,9,8,7,0 },
//	{ 1,2,3,4,5,9,7,8,6,0 },
//	{ 1,2,3,4,9,6,7,8,5,0 },
//	{ 1,2,3,9,5,6,7,8,4,0 },
//	{ 11,21,91,41,15,16,17,18,9,10 },
//	{ 1,9,3,4,5,6,7,8,2,0 },
//	{ 9,2,3,4,5,6,7,8,1,0 },
//	{ 1,2,3,4,5,6,7,8,0,9 }
//};

int saddle_point();

void main()
{
	int row_cnt, col_cnt;
	clock_t start;
	double duration;
	srand(time(NULL));

	// 위의 주석처리 된 행렬을 안장점 테스트용으로 쓸 수도 있지만
	// 온전한 프로그래밍을 위해 배열을 랜덤한 값으로 초기화시켜준다.
	for (row_cnt = 0; row_cnt < M_SIZE; row_cnt++)
	{
		for (col_cnt = 0; col_cnt < N_SIZE; col_cnt++)
		{
			arr[row_cnt][col_cnt] = rand() % 100 + 1;	// 1부터 100까지의 값으로 초기화
			printf("%4d", arr[row_cnt][col_cnt]);
		}
		putchar('\n');
	}

	// 아래는 알고리즘의 실행시간을 측정하는 과정이다.
	// 연산자체가 얼마 없기 때문에 요즘 컴퓨터에서라면 거의 0초 가까이 수렴해서 나올 것이다.
	// 위에 정의된 행렬의 행과 열을 더 늘리면서 테스트해보도록 하자.
	start = clock();
	saddle_point();
	duration = ((double)(clock() - start)) / CLOCKS_PER_SEC;
	printf("실행시간: %f\n", duration);

	return 0;
}

int saddle_point()
{
	int row, row_min_val, col_cnt, search_row_cnt, max_arr_num;

	for (row = 0; row < M_SIZE; row++)
	{
		row_min_val = arr[row][0];
		max_arr_num = 0;

		// 행에서 가장 작은 값을 찾는다.
		for (col_cnt = 1; col_cnt < N_SIZE; col_cnt++)
		{
			if (row_min_val > arr[row][col_cnt])
			{
				row_min_val = arr[row][col_cnt];

				// 가장 작은 값이 있는 열의 정보를 저장
				max_arr_num = col_cnt;
			}
		}

		// 현재 row_min_val에 row 행에서 가장 작은 값이 저장되어 있고
		// max_arr_num에 row_min_val이 저장되어 있는 열의 정보가 저장되어 있다.
		for (search_row_cnt = 0; search_row_cnt < M_SIZE; search_row_cnt++)	// 열을 고정한 채, 모든 행을 순환
		{
			// 만약 아래 조건문을 만족해서 break를 할 경우 현재 위치에 있는 값은 안장점이 아니다.
			// 행에서 가장 적고, 열에서 가장 커야 안장점인데 열에서 더 큰 값이 이미 존재하기 때문이다.
			if (row_min_val < arr[search_row_cnt][max_arr_num])
				break;
		}

		// 만약 위의 for문을 제대로 통과하여 search_row_cnt가 M_SIZE가 되었다면
		// 현재 위치의 점이 안장점이므로 안장점을 발견한 것이 된다.
		if (search_row_cnt >= M_SIZE)
		{
			printf("이 행렬의 안정점의 위치는 %d행 %d열 %d 이다.\n", row, max_arr_num, arr[row][max_arr_num]);
			return 1;
		}
	}
	puts("이 행렬은 안장점을 가지고 있지 않다.\n");
	return 0;
}

/*************************************************
 ** End Line
*************************************************/