[C++] 삼성 2105. [모의 SW 역량테스트] 디저트 카페

(2시간) 옛날에 풀어서 빨리 풀었는데 코드가 너무 안이뻐서 다른 방향으로 풀어볼려고 계속 붙잡았음.

4방향 모두 확인할 필요없이 앞에 두방향이 이동한만큼 반대로 backtracking 해주자는 생각으로 접근

 

#include<iostream>
#include<vector>

using namespace std;

int N;
int dessert[20][20];
int dir[4][2] = { {-1, 1}, {1, 1}, {1, -1}, {-1, -1} };
int dessertNum;

bool outRangeCheck(int x, int y) {
	if (x < 0 || y < 0 || x >= N || y >= N) return true;
	return false;
}

void dessertTour(int x, int y, vector<int> include, vector<int> path) {
	int direction = path.back();
	if (direction == 2) {
		// 두 방향을 이동했으면 두 방향이 이동한 만큼 반대편으로 backtracking
		path.pop_back();
		for (int i = 0; i < path.size(); i++) {
			x = x + dir[path[i] + 2][0];
			y = y + dir[path[i] + 2][1];
			int value = dessert[x][y];

			if (outRangeCheck(x, y)) return;

			for (int i = 0; i < include.size(); i++) {
				if (include[i] == value) return;
			}

			include.push_back(value);
		}

		int includeCount = include.size();

		if (dessertNum < includeCount)
			dessertNum = includeCount;

		return;
	}

	int new_x = x + dir[direction][0];
	int new_y = y + dir[direction][1];
	int value = dessert[new_x][new_y];

	if (outRangeCheck(new_x, new_y)) return;

	for (int i = 0; i < include.size(); i++) {
		if (include[i] == value) return;
	}

	include.push_back(value);

	path.push_back(direction);
	dessertTour(new_x, new_y, include, path);
	path.pop_back();

	path.push_back(direction + 1);
	dessertTour(new_x, new_y, include, path);
	path.pop_back();
}

int main() {
	int T;
	cin >> T;
	for (int t = 1; t <= T; t++) {
		cin >> N;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				cin >> dessert[i][j];
			}
		}

		dessertNum = -1;

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				vector<int> include;
				vector<int> path;
				path.push_back(0);
				dessertTour(i, j, include, path);
			}
		}
		cout << "#" << t << " " << dessertNum << endl;
	}
	return 0;
}