[SWEA] 디저트 카페

SWEA 디저트 카페 C++ 풀이

 

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5VwAr6APYDFAWu

 

// 브루트 포스 재귀 문제이다.
// 일단 마름모 꼴로 시계 방향으로 움직이는 dx, dy 선언하고
// 각 점마다 solve 함수를 실행을 하는데 시작하는 점을 따로 기억을 해줘야함
// 그래야 solve 함수 내에서 종료조건에서 비교할 수있음
// solve 함수에서 원래 방향을 진행하는 경우와 1씩 증가시키는 경우로 재귀함수 진행해 주자 여기가 포인트임

#include <iostream>
#include <algorithm>

using namespace std;

int map[21][21] = { 0, };
bool check[101] = { 0, };

int dx[] = { 1,1,-1,-1 };
int dy[] = { 1,-1,-1,1 };

int N, sx, sy, ans;

void solve(int x, int y, int cnt, int dir) {


	if (dir == 3) {
		if (x == sx + 1 && y == sy - 1) {
			ans = max(ans, cnt);
			return;
		}
	}

	int nx = x + dx[dir];
	int ny = y + dy[dir];

	if (nx >= 0 && nx < N && ny >= 0 && ny < N) {
		if (!check[map[nx][ny]]) {
			check[map[nx][ny]] = true;
			solve(nx, ny, cnt + 1, dir);
			solve(nx, ny, cnt + 1, dir + 1);
			check[map[nx][ny]] = false;
		}
	}
}

int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int T;

	cin >> T;

	for (int tc = 1; tc <= T; tc++) {

		ans = -1;

		cin >> N;

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				cin >> map[i][j];
			}
		}

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				sx = i, sy = j;
				check[map[i][j]] = true;
				solve(i, j, 1, 0);
				check[map[i][j]] = false;
			}
		}

		cout << "#" << tc << " " << ans << "\n";

	}

}