[알고리즘 잡스] offset (C++, 완전 탐색)

문제

5x5 2차원 배열이 주어질 때 어떤 원소가 상하좌우에 있는 원소보다 작을 때 해당 위치에 * 을 표시하는 프로그램을 작성하시오. 경계선에 있는 수는 상하좌우 중 존재하는 원소만을 비교한다.

 

입력

5x5 행렬의 정보가 25 개의 수로 주어진다. 각 수는 0 에서 9 사이 수이다.

 

출력

*를 포함한 행렬을 출력예의 형식으로 출력한다.

 

 

---

#include <iostream>
#include <vector>

#define MAX 10

using namespace std;

vector<vector <int>> arr(5, vector<int>(5, 0));
vector<vector <int>> chk(5, vector<int>(5, 0));

// 5x5 배열 입력 
void input() {
	for (int i = 0; i < 5; i++)
		for (int j = 0; j < 5; j++)
			cin >> arr[i][j];
}

// 입력받은 2차원 배열의 원소를 하나씩 검사하여 또 다른 2차원 배열 chk의 결과 저장
void compare() {

	// 사각형 각 꼭지점 원소 비교
	if (arr[0][0] < arr[1][0] && arr[0][0] < arr[0][1]) 
		chk[0][0] = MAX;
	if (arr[4][0] < arr[3][0] && arr[4][0] < arr[4][1]) 
		chk[4][0] = MAX;
	if (arr[4][4] < arr[3][4] && arr[4][4] < arr[4][3]) 
		chk[4][4] = MAX;
	if (arr[0][4] < arr[1][4] && arr[0][4] < arr[0][3]) 
		chk[0][4] = MAX;
	
	// 사각형의 꼭지점을 제외한 변 원소 비교
	for (int i = 1; i < 4; i++) {
		if (arr[i][0] < arr[i - 1][0] && arr[i][0] < arr[i + 1][0] && arr[i][0] < arr[i][1]) 
			chk[i][0] = MAX;
		if (arr[4][i] < arr[4][i - 1] && arr[4][i] < arr[4][i + 1] && arr[4][i] < arr[3][i]) 
			chk[4][i] = MAX;
		if (arr[i][4] < arr[i - 1][4] && arr[i][4] < arr[i + 1][4] && arr[i][4] < arr[i][3]) 
			chk[i][4] = MAX;
		if (arr[0][i] < arr[0][i + 1] && arr[0][i] < arr[0][i - 1] && arr[0][i] < arr[1][i]) 
			chk[0][i] = MAX;
	}

	int tmp;

	// 사각형 변 제외 내부 원소 비교
	for (int i = 1; i < 4; i++) {
		for (int j = 1; j < 4; j++) {
			tmp = arr[i][j];
			if (tmp < arr[i][j - 1] && tmp < arr[i][j + 1] && tmp < arr[i - 1][j] && tmp < arr[i + 1][j]) 
				chk[i][j] = MAX;
		}
	}
}

// 비교 결과가 저장된 chk 배열을 사용하여 출력
void print() {
	for (int i = 0; i < 5; i++) 
	{
		for (int j = 0; j < 5; j++) 
		{
			if (chk[i][j] == MAX)
				cout << "* ";
			else
				cout << arr[i][j] << " ";
		}
		cout << endl;
	}
}

int main() {

	ios_base::sync_with_stdio(false); 
	cin.tie(NULL); 
	cout.tie(NULL);
	
	input();
	compare();
	print();
}

 

완전 탐색을 기반으로 2차원 배열의 원소들을 검사하는 문제입니다. 코드의 길이를 줄이고 효율성을 높이기 위해 다른 방법으로 접근을 해보았으나, 5x5 2차원 배열이라는 정해진 크기가 주어져 있기 때문에 문제 자체에서는 완전 탐색을 사용하여 푸는 것이 가장 효율적인 것 같습니다.

 

 

꼭지점과 꼭지점을 제외한 변에 존재하는 원소를 검사하고 나서, 내부의 원소들을 검사할 때 처음에는 arr[i][j] * 4 < arr[i+1][j] + arr[i-1][j] + arr[i][j+1] + arr[i][j-1] 의 조건문을 삽입하여 접근하였습니다. 이 방법의 단점은 주변 원소 중에 숫자의 차이가 크게되면 부정확한 결과가 나오게 됩니다. 따라서 위와 같이 접근하여 푸는 것을 추천합니다.