[SWEA]2105 디저트 까페

2105 디저트 까페

풀이)

dfs를 이용해서 푼 문제이다.

최대한 중복되는 사각형 모양을 거르기 위해 두가지 방법을 사용했다.

1. 맨왼쪽, 맨오른쪽, 맨아래쪽에서 시작하는 경우는 사각형을 이루지 못하므로 계산에서 제외한다.

2. 사각형으로 움직일때, 무조건 오른쪽 아래부터 시작한다.

주의할 점

출발점으로 돌아왔을때, 디저트의 수는 무조건 4개 이상이며 방향으로 제일 마지막 방향 상태여야한다.

코드)

#include <stdio.h>
#include <algorithm>
using namespace std;
 
int n;
int map[21][21];
int starty, startx; //시작점
//방향 0        1       2        3
//오른쪽아래, 왼쪽아래, 왼쪽위, 오른쪽위
int dy[4] = { 1,1,-1,-1 };
int dx[4] = { 1,-1,-1,1 };
int    result = -1;
bool check[101];
 
//현재 좌표, 가는 방향, 지금까지 디저트 개수
void dfs(int y,int x, int dir,int val) {
    if (dir > 3)return;
 
    int ny = y + dy[dir];
    int nx = x + dx[dir];
    if (ny == starty && nx == startx && val >= 4 && dir==3) { //출발점으로 돌아왔을 경우
        result = max(result, val);
        return;
    }
    if (ny >= 0 && ny < n && nx >= 0 && nx < n) {
        if (!check[map[ny][nx]]) {
            check[map[ny][nx]] = true;
            dfs(ny, nx, dir, val + 1);// 가던 방향 계속
            dfs(ny, nx, dir + 1, val + 1); //방향 바꿈
            check[map[ny][nx]] = false;
        }
    }
    
}
 
int main() {
    //freopen("sample_input.txt", "r", stdin);
    int T = 0;
    scanf("%d", &T);
    for (int test_case = 1; test_case <= T; test_case++) {
        scanf("%d", &n);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                scanf("%d", &map[i][j]);
            }
        }
        //n은 4<=n<=20
        for (int i = 0; i < n-1; i++) {
            for (int j = 1; j < n-1; j++) {
                check[map[i][j]] = true;
                starty = i;
                startx = j;
                dfs(i, j, 0, 1);
                check[map[i][j]] = false;
            }
        }
        printf("#%d %d\n", test_case, result);
        result = -1;
    }
 
    
 
    return 0;
}