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

※ SW Expert 아카데미의 문제를 무단 복제하는 것을 금지합니다.


친구들과 디저트 카페 투어를 할 계획이다.

[Fig. 1]과 같이 한 변의 길이가 N인 정사각형 모양을 가진 지역에 디저트 카페가 모여 있다.

원 안의 숫자는 해당 디저트 카페에서 팔고 있는 디저트의 종류를 의미하고
카페들 사이에는 대각선 방향으로 움직일 수 있는 길들이 있다.
디저트 카페 투어는 어느 한 카페에서 출발하여
[Fig. 2]와 같이 대각선 방향으로 움직이고 사각형 모양을 그리며 출발한 카페로 돌아와야 한다.
 
 

디저트 카페 투어를 하는 도중 해당 지역을 벗어나면 안 된다.
또한, 친구들은 같은 종류의 디저트를 다시 먹는 것을 싫어한다.
즉, [Fig. 3]과 같이 카페 투어 중에 같은 숫자의 디저트를 팔고 있는 카페가 있으면 안 된다.
 

[Fig. 4]와 같이 하나의 카페에서 디저트를 먹는 것도 안 된다.
 

[Fig. 5]와 같이 왔던 길을 다시 돌아가는 것도 안 된다

 

친구들과 디저트를 되도록 많이 먹으려고 한다.
디저트 가게가 모여있는 지역의 한 변의 길이 N과 디저트 카페의 디저트 종류가 입력으로 주어질 때,
임의의 한 카페에서 출발하여 대각선 방향으로 움직이고
서로 다른 디저트를 먹으면서 사각형 모양을 그리며 다시 출발점으로 돌아오는 경우,
디저트를 가장 많이 먹을 수 있는 경로를 찾고, 그 때의 디저트 수를 정답으로 출력하는 프로그램을 작성하라.
만약, 디저트를 먹을 수 없는 경우 -1을 출력한다.

[예시]
한 변의 길이 N이 4인 지역에 디저트 카페가 [Fig. 6]과 같이 있다고 생각하자

디저트 카페 투어가 가능한 경우는 [Fig. 7]과 같이 5가지로 나눌 수 있다.
(출발한 곳과 도는 방향은 다를 수 있지만, 디저트 카페 투어의 경로가 그리는 사각형 모양은 5가지 중 하나이다.)

 

[Fig. 7]

 
이 중에 디저트를 가장 많이 먹을 수 있는 경우는 ⑤인 경우로 디저트의 종류는 6개이다.
따라서, 정답은 6이 된다.


[제약사항]

1. 시간제한 : 최대 50개 테스트 케이스를 모두 통과하는 데 C/C++/Java 모두 3초
2. 디저트 카페가 모여있는 지역의 한 변의 길이 N은 4 이상 20 이하의 정수이다. (4 ≤ N ≤ 20)
3. 디저트 종류를 나타나는 수는 1 이상 100 이하의 정수이다.


[입력]

입력의 맨 첫 줄에는 총 테스트 케이스의 개수 T가 주어지고, 그 다음 줄부터 T개의 테스트 케이스가 주어진다.
각 테스트 케이스의 첫 번째 줄에는 디저트 카페가 모여있는 지역의 한 변의 길이 N이 주어진다.
그 다음 N 줄에는 N * N 크기의 디저트 카페에서 팔고 있는 디저트 종류에 대한 정보가 주어진다.


[출력]

테스트 케이스 개수만큼 T개의 줄에 각각의 테스트 케이스에 대한 답을 출력한다.
각 줄은 "#t"로 시작하고 공백을 하나 둔 다음 정답을 출력한다. (t는 1부터 시작하는 테스트 케이스의 번호이다)
출력해야 할 정답은 가능한 경우 중 디저트를 가장 많이 먹을 때의 디저트 수 이다.
만약, 디저트를 먹을 수 없는 경우 정답은 -1이다.

 

 

#include <iostream>
#include <string.h>
using namespace std;
 
bool dessert[101];
int arr[21][21],ans, mx[] = {1,1,-1,-1}, my[] = {1, -1, -1, 1};
int target_x, target_y,n;
void solve(int x, int y,int len, int dir)
{
 
    if(x == target_x && y == target_y)
    {
        if(len>ans)
            ans = len;
        return;
    }
    for(int i=dir;i<4;i++)
    {
        int nx = x + mx[i];
        int ny = y + my[i];
        if(nx<0||ny<0||nx>=n||ny>=n||dessert[arr[nx][ny]])
        {
            continue;
        }
        dessert[arr[nx][ny]] = true;
        solve(nx, ny, len + 1, i);
        dessert[arr[nx][ny]] = false;
    }
 
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    int tc;
    cin>>tc;
    for(int t=1;t<=tc;t++)
    {
        memset(arr, 0, sizeof(arr));
        ans = 0;
        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-1;i++)
            for(int j=1;j<n-1;j++)
            {
                memset(dessert, false, sizeof(dessert));
                target_x = i + 1;
                target_y = j - 1;
                dessert[arr[i][j]] = true;
                solve(i,j,0,0);
 
            }
 
        if(ans<3)
            cout<<'#'<<t<<' '<<-1<<'\n';
        else
            cout<<'#'<<t<<' '<<ans + 1<<'\n';
 
    }
    return 0;
}
 

30분 걸렸다... 나 너무 멍청한가봐

15분동안 다 짰는데 마지막 solve하기 전에 출발지를 true를 해놔야 하는데

저 두 줄을 바꾸어 쓰는 바람에 15분 헤맸다... ㅋㅋㅋ

 

알고리즘

1.  회전 순서는 오른쪽 아래, 왼쪽 아래, 왼쪽 위, 오른쪽 위 순으로 돌아간다.

그 이전으로는 돌아가지 않는다. 그래서 solve의 for문 안에 i가 dir부터 시작한다.

2. dfs를 돌리기전에 목표 장소가 시작 장소의 x좌표 + 1, y좌표 -1이어서 target x, y,를 설정한다.

이렇게 안하고 원래 좌표로 돌아오게 하려면 첫 번째 true를 잘 바꿔야 할것이다. 난 귀찮아서 이렇게 했다.

암튼 첫 시작 지점의 디저트를 먹었다고 표시한 후, dfs를 돌린다.

3. 탐색을 시작한다. 다음 방문할 지점을 방문할 수 있으면 방문하고 그렇지 못하면 방향을 바꾼다.

4. 출력을 하기전에 방문 길이가 1 차이나는 지점에서 끊었기 때문에 1을 더해준다.