[SWEA] #2105 _ 디저트 카페

[디저트 카페] https://swexpertacademy.com/main/code/problem/problemDetail.do

SW Expert Academy

start[2]에 시작점의 좌표를 저장해주었고, dessert 배열을 이용하여 먹은 디저트를 체크해주었다.

(디저트의 종류는 1부터 시작한다는 점에 유의하자!)

또한, dfs를 이용하여 모든 경우의 수를 고려하여 구현하였다.

 

[ 소스 코드 ]

#include <cstdio>
#include <vector>
#include <algorithm>
#define MAX 20

using namespace std;

int dx[] = { 1, -1, -1, 1 }, dy[] = { 1, 1, -1, -1 };
int N, max_dessert, start[2];
int dessert[101], map[MAX][MAX];

void solve(int y, int x, int d, int cnt);
int main() {
	int T;

	scanf("%d", &T);
	for (int i = 1; i <= T; i++) {
		scanf("%d", &N);
		for (int j = 0; j < N; j++) {
			for (int k = 0; k < N; k++) scanf("%d", &map[j][k]);
		}

		max_dessert = -1;

		for (int i = 0; i < N - 2; i++) {
			for (int j = 1; j < N - 1; j++) {
				start[0] = i;
				start[1] = j;
				dessert[map[i][j]] = 1;
				solve(i, j, 0, 1);
				dessert[map[i][j]] = 0;
			}
		}

		printf("#%d %d\n", i, max_dessert);
	}

	return 0;
}

void solve(int y, int x, int d, int cnt) {
	y += dy[d];
	x += dx[d];

	if (y == start[0] && x == start[1]) {
		max_dessert = max(max_dessert, cnt);
		return;
	}
	if (x < 0 || y < 0 || x >= N || y >= N) return;
	if (dessert[map[y][x]]) return;

	dessert[map[y][x]] = 1;
	solve(y, x, d, cnt + 1);
	if(d < 3) solve(y, x, d + 1, cnt + 1);
	dessert[map[y][x]] = 0;
}