2819. 격자판의 숫자 이어 붙이기

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

SW Expert Academy

 

직관적으로 풀었는데 맞았다. 행렬 크기가 고정되어있고 사이즈가 작아서 시간초과가 안나는 것 같다.

 

#include<iostream>
#include<vector>
#include<map>
#include<string>
using namespace std;

char arr[4][4];
vector<char> vec;
map<string, bool> m;
int result;

void DFS(int y, int x)
{
	if (vec.size() == 7)
	{
		string str;
		for (int i = 0; i < vec.size(); i++)
		{
			str += vec[i];
		}

		if (!m[str])
		{
			result++;
			m[str] = true;
		}

		return;
	}


	if (y + 1 < 4)
	{
		vec.push_back(arr[y + 1][x]);
		DFS(y + 1, x);
		vec.pop_back();
	}

	if (y - 1 >= 0)
	{
		vec.push_back(arr[y - 1][x]);
		DFS(y - 1, x);
		vec.pop_back();

	}

	if (x + 1 < 4)
	{
		vec.push_back(arr[y][x+1]);
		DFS(y , x+1);
		vec.pop_back();
	}

	if (x - 1 >= 0)
	{
		vec.push_back(arr[y][x-1]);
		DFS(y, x-1);
		vec.pop_back();
	}
}

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

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

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


		

		for (int i = 0; i < 4; i++)
		{
			for (int j = 0; j < 4; j++)
			{
				vec.push_back(arr[i][j]);
				DFS(i, j);
				vec.pop_back();

			}
		}

		cout << "#" << test_case << " " << result << endl;
		

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