7699. 수지의 수지 맞는 여행

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWqUzj0arpkDFARG&categoryId=AWqUzj0arpkDFARG&categoryType=CODE

SW Expert Academy

 

간단한 DFS 문제. map쓰면 시간초과 배열로 해결.

 

/////////////////////////////////////////////////////////////////////////////////////////////
// 기본 제공코드는 임의 수정해도 관계 없습니다. 단, 입출력 포맷 주의
// 아래 표준 입출력 예제 필요시 참고하세요.
// 표준 입력 예제
// 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<map>
using namespace std;

char arr[20][20];
bool visit[20][20];
int R, C;
int maxa;
bool m[26];

void DFS(int y, int x, int count)
{
	bool flag = false;

	if (y - 1 >= 0 && !visit[y - 1][x])
	{
		visit[y - 1][x] = true;

		if (!m[arr[y - 1][x]- 'A'])
		{
			m[arr[y - 1][x] - 'A'] = true;
			DFS(y - 1, x, count + 1);
			m[arr[y - 1][x]- 'A'] = false;
		}
		

		visit[y - 1][x] = false;
	}

	if (y + 1 < R && !visit[y + 1][x])
	{
		visit[y + 1][x] = true;

		if (!m[arr[y + 1][x]- 'A'])
		{
			m[arr[y + 1][x]- 'A'] = true;
			DFS(y + 1, x, count + 1);
			m[arr[y + 1][x]- 'A'] = false;
		}
		

		visit[y + 1][x] = false;
	}

	if (x - 1 >= 0 && !visit[y][x - 1])
	{
		visit[y][x - 1] = true;

		if (!m[arr[y][x - 1]- 'A'])
		{
			m[arr[y][x - 1]- 'A'] = true;
			DFS(y, x - 1, count + 1);
			m[arr[y][x - 1]- 'A'] = false;
		}
	

		visit[y][x - 1] = false;
	}

	if (x + 1 < C && !visit[y][x + 1])
	{
		visit[y][x + 1] = true;

		if (!m[arr[y][x + 1]- 'A'])
		{
			m[arr[y][x + 1]- 'A'] = true;
			DFS(y, x + 1, count + 1);
			m[arr[y][x + 1]- 'A'] = false;
		}

		visit[y][x + 1] = false;

	}

	if (!flag)
	{
		if (count > maxa)
		{
			maxa = count;
		}
		return;

	}
}

int main(int argc, char** argv)
{
	int test_case;
	int T;

	cin >> T;
	/*
	   여러 개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
	*/
	for (test_case = 1; test_case <= T; ++test_case)
	{

		cin >> R >> C;
		
		maxa = 0;
		memset(visit, 0, sizeof(visit));
        memset(m,0,sizeof(m));

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

		m[arr[0][0]- 'A'] = true;
		visit[0][0] = true;
		DFS(0, 0, 1);

		cout << "#" << test_case << " " << maxa << endl;
	}
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}