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

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

SW Expert Academy

 

한가지의 방향으로만 순회해도 풀리는 문제.

먹는 디저트의 순서가 상관없기 때문.

 

 

/////////////////////////////////////////////////////////////////////////////////////////////
// 기본 제공코드는 임의 수정해도 관계 없습니다. 단, 입출력 포맷 주의
// 아래 표준 입출력 예제 필요시 참고하세요.
// 표준 입력 예제
// int a;
// float b, c;
// double d, e, f;
// char g;
// char var[256];
// long long AB;
// cin >> a;                            // int 변수 1개 입력받는 예제
// cin >> b >> c;                       // float 변수 2개 입력받는 예제 
// cin >> d >> e >> f;                  // double 변수 3개 입력받는 예제
// cin >> g;                            // char 변수 1개 입력받는 예제
// cin >> var;                          // 문자열 1개 입력받는 예제
// cin >> AB;                           // long long 변수 1개 입력받는 예제
/////////////////////////////////////////////////////////////////////////////////////////////
// 표준 출력 예제
// int a = 0;                            
// float b = 1.0, c = 2.0;               
// double d = 3.0, e = 0.0; f = 1.0;
// char g = 'b';
// char var[256] = "ABCDEFG";
// long long AB = 12345678901234567L;
// cout << a;                           // int 변수 1개 출력하는 예제
// cout << b << " " << c;               // float 변수 2개 출력하는 예제
// cout << d << " " << e << " " << f;   // double 변수 3개 출력하는 예제
// cout << g;                           // char 변수 1개 출력하는 예제
// cout << var;                         // 문자열 1개 출력하는 예제
// cout << AB;                          // long long 변수 1개 출력하는 예제
/////////////////////////////////////////////////////////////////////////////////////////////

#include<iostream>
#include<string.h>
#include<queue>
using namespace std;
int N;
int result, cur;
int starty, startx;
int arr[20][20];
bool visit[20][20];
bool disert[101];
bool flag;

int dir; // 1 왼아래 2 오아래 3 오위 4 왼위

void DFS(int y, int x)
{
	

	if (dir == 1)
	{
		if (y + 1 < N && x - 1 >= 0)
		{
			if (!visit[y + 1][x - 1] && !disert[arr[y+1][x-1]])
			{
				visit[y + 1][x - 1] = true;
				disert[arr[y+1][x-1]] = true;
				cur++;
				dir = 1;
				DFS(y + 1, x - 1);
				visit[y + 1][x - 1] = false;
				disert[arr[y + 1][x - 1]] = false;
				cur--;

			}
		}

		if (y + 1 < N && x + 1 < N)
		{
			if (!visit[y + 1][x + 1] && !disert[arr[y + 1][x + 1]])
			{
				visit[y + 1][x + 1] = true;
				disert[arr[y + 1][x + 1]] = true;
				cur++;
				dir = 2;
				DFS(y + 1, x + 1);
				visit[y + 1][x + 1] = false;
				disert[arr[y + 1][x + 1]] = false;
				cur--;
			}
		}
	}
	else if (dir == 2)
	{
		if (y + 1 < N && x + 1 < N)
		{
			if (!visit[y + 1][x + 1] && !disert[arr[y + 1][x + 1]])
			{
				visit[y + 1][x + 1] = true;
				disert[arr[y + 1][x + 1]] = true;
				cur++;
				dir = 2;
				DFS(y + 1, x + 1);
				visit[y + 1][x + 1] = false;
				disert[arr[y + 1][x + 1]] = false;
				cur--;
			}
		}

		if (y - 1 >= 0 && x + 1 < N)
		{
			if (!visit[y - 1][x + 1] && !disert[arr[y - 1][x + 1]])
			{
				visit[y - 1][x + 1] = true;
				disert[arr[y - 1][x + 1]] = true;
				cur++;
				dir = 3;
				DFS(y - 1, x + 1);
				visit[y - 1][x + 1] = false;
				disert[arr[y - 1][x + 1]] = false;
				cur--;

			}
		}

	}
	else if (dir == 3)
	{
		if (y - 1 >= 0 && x + 1 < N)
		{
			if (!visit[y - 1][x + 1] && !disert[arr[y - 1][x + 1]])
			{
				visit[y - 1][x + 1] = true;
				disert[arr[y - 1][x + 1]] = true;
				cur++;
				dir = 3;
				DFS(y - 1, x + 1);
				visit[y - 1][x + 1] = false;
				disert[arr[y - 1][x + 1]] = false;
				cur--;

			}
		}


		if (y - 1 >= 0 && x - 1 >= 0)
		{
			if (!visit[y - 1][x - 1] && !disert[arr[y - 1][x - 1]])
			{
				visit[y - 1][x - 1] = true;
				disert[arr[y - 1][x - 1]] = true;
				cur++;
				dir = 4;
				DFS(y - 1, x - 1);
				visit[y - 1][x - 1] = false;
				disert[arr[y - 1][x - 1]] = false;
				cur--;

			}
			else
			{
				if (y - 1 == starty && x - 1 == startx && cur)
				{
					flag = true;
					if (cur > result)
					{
						result = cur;
					}
					return;
				}
			}
		}

	}
	else if (dir == 4)
	{
		if (y - 1 >= 0 && x - 1 >= 0)
		{
			if (!visit[y - 1][x - 1] && !disert[arr[y - 1][x - 1]])
			{
				visit[y - 1][x - 1] = true;
				disert[arr[y - 1][x - 1]] = true;
				cur++;
				dir = 4;
				DFS(y - 1, x - 1);
				visit[y - 1][x - 1] = false;
				disert[arr[y - 1][x - 1]] = false;
				cur--;

			}
			else
			{
				if (y -1  == starty && x -1 == startx && cur)
				{
					flag = true;
					if (cur > result)
					{
						result = cur;
					}
					return;
				}
			}
		}

	}
}


int main(int argc, char** argv)
{
	int test_case;
	int T;
	
	cin >> T;
	/*
	   여러 개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
	*/
	for (test_case = 1; test_case <= T; ++test_case)
	{	
		cin >> N;
		memset(visit, 0, sizeof(visit));
		memset(disert, 0, sizeof(disert));
		result = 0;
		flag = false;
		

		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < N; j++)
			{
				cin >> arr[i][j];
			}
		}

		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < N; j++)
			{
				dir = 1;
				cur = 1;
				starty = i;
				startx = j;
				visit[i][j] = true;
				disert[arr[i][j]] = true;
				DFS(i, j);
				disert[arr[i][j]] = false;
				visit[i][j] = false;
			}
		}

		if (!flag)
		{
			cout << "#" << test_case << " " << -1 << endl;
		}
		else
		{
			cout << "#" << test_case << " " << result << endl;
		}

		

	

	}
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}