디저트 카페
문제 해석
NxN크기의 디저트 카페가 있을 때, 가장 많이 먹을 수 있는 디저트 수를 구하는 문제입니다.
디저트 카페 투어는 어느 한 카페에서 출발하여 대각선 방향으로 움직이고 사각형 모양을 그리며 출발한 카페로 돌아와야 합니다.
카페 투어 중 같은 숫자의 디저트를 팔고 있는 카페가 있으면 안됩니다.
설계(5)
시작지점을 선정(O(N^2))하고 가능한 모든 경로를 탐색하는 완전탐색문제입니다.
먼저 시작지점을 선택합니다.
오른쪽 아래 대각선 방향으로 시작해서 방향을 바꾸는 경우와 그대로 진행하는 경우 두가지에 대해 탐색을 진행합니다.
범위를 넘어서거나 디저트를 이미 먹은 숫자가 나오면 해당 경로는 탐색하지 않습니다.
단, 시작위치로 되돌아오는 경우를 생각해야하기 때문에 이동할 위치가 시작위치면 예외적으로 탐색하도록 해줘야 합니다
각 방향으로 몇번 이동하였는지 len배열에 카운트를 해둡니다.
만약 시작 위치로 돌아왔을 때(기저사례), len배열이 모두 0보다 크고 각각 변의 길이가 같으면 최댓값을 갱신합니다.
구현(15)
코드
#include <iostream>
using namespace std;
#define MAXN 20
int used[101];
int arr[MAXN][MAXN];
int N;
int len[4];
int dx[] = { 1,1,-1,-1 };
int dy[] = { 1,-1,-1,1 };
int sx, sy;
int ans;
void dfs(int x, int y, int dir,int cnt) {
if (x == sx && y == sy) {
if (len[0] > 0 && len[1] > 0 && len[2] > 0 && len[3] > 0) {
if (len[0] == len[2] && len[1] == len[3]) {
if (ans < cnt) ans = cnt;
}
return;
}
}
used[arr[x][y]] = 1;
for (int i = 0; i < 2; i++) {
if (!i&& len[dir]>0) {
if (dir != 3) {
int n_dir = (dir + 1) % 4;
int nx = x + dx[n_dir];
int ny = y + dy[n_dir];
if (nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
if ((nx == sx && ny == sy) || !used[arr[nx][ny]]) {
len[n_dir]++;
dfs(nx, ny, n_dir, cnt + 1);
len[n_dir]--;
}
}
}
else if (i) {
int nx = x + dx[dir];
int ny = y + dy[dir];
if (nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
if ((nx == sx && ny == sy) || !used[arr[nx][ny]]) {
len[dir]++;
dfs(nx, ny, dir, cnt + 1);
len[dir]--;
}
}
}
used[arr[x][y]] = 0;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
for (int test_case = 1; test_case <= t; test_case++) {
ans = -1;
cin >> N;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cin >> arr[i][j];
}
}
for (int i = 0; i < N - 2; i++) {
for (int j = 1; j < N - 1; j++) {
sx = i;
sy = j;
dfs(i, j, 0, 0);
}
}
printf("#%d %d\n", test_case, ans);
}
return 0;
}
디버깅
시작위치로 되돌아오는 경우를 처리하지 않는 실수를 하였습니다.
제출결과
51 ms
마무리
재귀적 특성을 이용하는 완전탐색 문제였습니다.
재귀 부분을 생각하기가 약간 까다로워서 개인적으로 꼭 한번 풀어봐야하는 문제라고 생각합니다.