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

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

SW Expert Academy

출발할 수 있는 모든 칸에서부터 출발하여  대각선 방향으로 움직이고 사각형 모양을 그리며 출발한 카페로 돌아온다.

n-1행, n-2행, 0열, n-1열인 곳에서는 사각형을 만들 수 없으므로 출발할 수 없다.

 

각 칸에서 출발하면 오른쪽아래(1,1), 왼쪽 아래(1,-1), 왼쪽 위(-1,-1), 오른쪽 위(-1,1)의 순서로 사각형을 그리도록 했다.

시작점인 경우에만 현재 방향을 유지해서 진행하고 그렇지 않은 경우에는

방향을 꺾어서 이동하는 경우와 현재 방향을 유지한채로 이동하는 경우를 모두 탐색했다.

 

같은 종류의 디저트를 먹으면 안되므로 디저트의 종류를 인덱스로 방문 체크를 해준다.

이동할 곳의 디저트를 아직 먹지 방문하지 않았다면 방문 체크를 해주고 다음 칸으로 이동한다.

이동할 때마다 디저트의 개수를 세주기 위해서  cnt 값을 +1 해서 넘겨준다.

 

이동하다가 이미 방문한 디저트 카페 이지만 그곳이 시작점인 경우에는 출발한 카페로 돌아온 경우이므로

그때까지의 방문한 디저트의 수를 비교해준다.

 

#include <iostream>
#include <cstring>
using namespace std;
 
int n, ans;
int sx, sy;
int map[20][20];
int dx[] = {1,1,-1,-1};
int dy[] = { 1,-1,-1,1 };
bool check[101];
 
void solve(int x, int y, int dir, int cnt) {
    
 
    //시작점인 경우
    if (x == sx && y == sy) {
    
            int nx = x + dx[dir];
            int ny = y + dy[dir];
            if (check[map[nx][ny]] == false) {
                check[map[nx][ny]] = true;
                solve(nx, ny, dir,cnt+1);
                check[map[nx][ny]] = false;
            }    
        
    }
    else {
 
        
        //현재 방향 유지하는 경우
        int nx = x + dx[dir];
        int ny = y + dy[dir];
        if (nx >= 0 && ny >= 0 && nx < n && ny < n) {
            if (check[map[nx][ny]] == false) {
                check[map[nx][ny]] = true;
                solve(nx, ny, dir, cnt+1);
                check[map[nx][ny]] = false;
            }
            else if (nx == sx && ny == sy) {
                //방문 표시가 되어있지만 출발점인 경우
                if (ans < cnt) {
                    ans = cnt;
                }
            }
        }
 
 
 
        //방향을 꺾는 경우
        dir += 1;
        if(dir > 3) return;
        nx = x + dx[dir];
        ny = y + dy[dir];
        if (nx >= 0 && ny >= 0 && nx < n && ny < n) {
            if (check[map[nx][ny]] == false) {
                check[map[nx][ny]] = true;
                solve(nx, ny, dir, cnt+1);
                check[map[nx][ny]] = false;
            }
            else if (nx == sx && ny == sy) {
                //방문 표시가 되어있지만 출발점인 경우
                if (ans < cnt) {
                    ans = cnt;
                }
            }
        }
    }
    
 
 
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int T;
    cin >> T;
    
    for (int tc = 1; tc <= T; tc++) {
        cin >> n;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                cin >> map[i][j];
            }
        }
 
        ans = -1;
        memset(check, false, sizeof(check));
 
        //시작점
        for (int i = 0; i < n - 2; i++) {
            for (int j = 1; j < n - 1; j++) {
                sx = i;
                sy = j;
                check[map[i][j]] = true;
                solve(sx,sy,0,1);
                check[map[i][j]] = false;
                
            }
        }
 
        cout << '#' << tc << ' ' << ans << '\n';
    }
 
    return 0;
}