[SWEA] 디저트가게

[문제]

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

SW Expert Academy

[풀이방법]

1) 대각선 방향으로 이동 하여 시작점으로 다시 되돌아 오는 루트이다. 

2) 같은 수의 디저트를 파는 가게를 들리지 않는다. (bool 배열로 처리)

3) 하나의 카페에서 사이클 돌면 안된다. 

4) 사각형 모양을 그리며 투어를 해야한다. 

5) 왔던 길을 되돌아 가면 안된다. 

 

* 사이클  = 방향을 4번 전환한다. 

* 사각형으로 사이클을 형성하는 경우에 시계 방향 / 반시계 방향으로만 진행되기 때문에 평소 좌표 이동처럼 4번을 반복하지 않고 2번만 반복한다. 

 

* 각 기준점을 시작으로 투어를 할 때 예전의 visited와 가게의 디저트 수가 true일 경우에는 갈 수 없도록 했기 때문에 

백트래킹을 사용해야 한다. 

 

visited[][] = true

dessert[]= true

dfs()

visited[][] = false

dessert[] = false

 

* 시작점으로 다시 되돌아 올 경우를 고려해야 한다. 

cnt 변수를 두어 시작 좌표와 동일할 때 cnt > 1 인 경우에는 사각형을 형성하고 다시 되돌아 온 경우이기 때문에

cnt와 최대비교를 통해 정답을 도출해준다. 

그 외에 nx,  ny가 시작점과 같을 경우에는 다시 dfs를 호출한다. (이 때, 이미 visited와 dessert가 true이기 때문에 중간에 걸리지 않게 주의한다.)

 

*개인적인 생각 

ccw와 연관지어서 나올 수 있을까..? (가장 큰 사각형.. 정도로)

 

---

 

#include <iostream>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>
 
using namespace std;
 
int n;
int map[20][20];
bool visited[20][20];
 
//대각선으로 이동
int dx[4] = {1, 1, -1, -1};
int dy[4] = {1, -1, -1, 1};
 
bool dessert[101]; //각 카페에서 파는 디저트의 최대 수
int ans, sx, sy;
 
void dfs(int x, int y, int dir, int cnt)
{
    //사이클을 형성했는지 확인해야 한다.
    if (dir == 4) //사이클을 형성하려면 총 4번 회전한다.
    {
        if (x == sx && y == sy && cnt > 1) //시작하자마자 되돌아옴이 아님을 보장
        {
            //사이클을 돌아 시작점으로 다시 돌아온 경우(디저트 가게를 정상적으로 순회함)
            ans = max(ans, cnt);
        }
        return;
    }
 
    for (int i = 0; i < 2; i++)
    {
        int nx = x + dx[dir];
        int ny = y + dy[dir];
 
        //이전에 나온 디저트 수와 같지 않아야 한다.
        if (nx >= 0 && nx < n && ny >= 0 && ny < n && !visited[nx][ny] && !dessert[map[nx][ny]]) {
            visited[nx][ny] = true;
            dessert[map[nx][ny]] = true;
            dfs(nx, ny, dir + i, cnt + 1);
            visited[nx][ny] = false;
            dessert[map[nx][ny]] = false;
        }
        
        else if (nx == sx && ny == sy) //visited, dessert가 true임 
        {
            //바로 되돌아간 경우
            dfs(nx, ny, dir + i, cnt + 1);
        }
    }
}
 
void init()
{
    memset(map, 0, sizeof(map));
    memset(visited, false, sizeof(visited));
    memset(dessert, false, sizeof(dessert));
    ans = 0;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int t;
 
    cin >> t;
 
    for (int tc = 1; tc <= t; tc++)
    {
        init();
        cin >> n;
 
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                cin >> map[i][j];
            }
        }
        //입력
 
        //정답이 없을 경우 -1 출력
 
        //사각형 모양으로 투어를 해야한다.
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
 
                sx = i;
                sy = j;
                visited[i][j] = true;
                dessert[map[i][j]] = true;
                dfs(i, j, 0, 0);
                visited[i][j] = false;
                dessert[map[i][j]] = false;
            }
        }
        if (ans == 0) ans = -1;
        cout << "#" << tc << " " << ans << '\n';
    }
    return 0;
}