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

아..어려웠다. 어려웠어~ 사각형 만들어 주는게 안 떠올랐어~~

접근법

1. N*N의 모든 맵에 대해서 탐색을 해주어야 한다.

2. 사각형 모양으로 탐색을 해야 한다.

사각형 모양으로 탐색하는 방법.

우하 -> 좌하 -> 좌상 -> 우상   방향으로 dx,dy 배열 설정. 그럼 0:우하, 1:좌하, 2: 좌상, 3: 우상 이 된다.

그리고 0->1->2->3 순서로만 탐색하도록 if문 조절만 해주면 된다.

그래서!!DFS문 for문 시작은 현재 방향부터, 그리고 현재 방향과 다음 방향은 항상 1차이 이하일 때만 탐색 시작.

#include <stdio.h>
#include <string.h>
 
int map[24][24], visit[24][24], direction[5], desert[101], MAX, N;
int dx[] = { 1,-1,-1,1 };
int dy[] = { 1,1,-1,-1 };
 
void DFS(int y, int x, int n, int d, int S_y, int S_x)
{
    for (int i = d; i < 4; i++)
    {
        int yy = y + dy[i];
        int xx = x + dx[i];
 
        if (yy == S_y && xx == S_x && n >= 4)
        {
            if (MAX < n)
                MAX = n;
            return;
        }
 
        if (map[yy][xx] == -1 || visit[yy][xx] == 1 || desert[map[yy][xx]] == 1 || (i-d<0 ? -1*(i-d):i-d) > 1)
            continue;
 
        visit[yy][xx] = desert[map[yy][xx]] = 1;
        DFS(yy, xx, n + 1, i, S_y, S_x);
        visit[yy][xx] = desert[map[yy][xx]] = 0;
    }
    return;
}
 
int main()
{
    int Test_Case;
    scanf("%d", &Test_Case);
 
    for (int T = 1; T <= Test_Case; T++)
    {
        memset(desert, 0, sizeof(desert));
        memset(direction, 0, sizeof(direction));
        memset(visit, 0, sizeof(visit));
        memset(map, -1, sizeof(map));
        MAX = -987654321;
        scanf("%d", &N);
 
        for (int i = 1; i <= N; i++)
            for (int j = 1; j <= N; j++)
                scanf("%d", &map[i][j]);
 
        for (int i = 1; i <= N; i++)
        {
            for (int j = 1; j <= N; j++)
            {
                visit[i][j] = desert[map[i][j]] = 1;
                DFS(i, j, 1, 0, i, j);
                visit[i][j] = desert[map[i][j]] = 0;
            }
        }
        if (MAX == -987654321)
        {
            printf("#%d %d\n", T, -1);
            continue;
        }
        printf("#%d %d\n", T, MAX);
    }
 
    return 0;
}