테트로미노 - 14500 (Solve 2)

문제 : https://www.acmicpc.net/problem/14500

14500번: 테트로미노

기존에는 해당 도형들의 회전된 모든 경우의 수를 구하여서 배열에 적재 후 이를 탐색하여 해결을 하였다.

이 방법도 속도가 빠르고 괜찮은 방법이긴한데 하나라도 회전한 경우의 수를 못찾으면 문제를 틀리는 상황이 발생한다.

알아보니 DFS 방식으로도 풀길래 한번 시도를 해보았는데... 생각보다 오래걸렸다..

지금부터 왜 시간이 오래걸렸는지 하나씩 썰을 풀어보겠다.

일단 처음에는 DFS특성처럼 매개변수로 입력받은 하나의 도형을 기준으로 상하좌우를 탐색하여 경우의 수를 찾았다.

탈출조건 : Stack의 크기가 4이면 합의 크기를 비교한다음 크면 저장.

다음경우 :  입력받은 도형을 기준으로 상하좌우 탐색루프를 돌면서 범위에 충족되면 재귀호출.

이렇게 생각을 한다음 코드를 짰다.

실패코드 : 

#include <iostream>
#include <stack>
#include <limits>

using namespace std;
int num[501][501] = { 0 };
bool check[501][501] = { false };
int value = INT32_MIN;
int n, m;
int xMove[4] = { -1,1,0,0 };
int yMove[4] = { 0,0,-1,1 };
stack<std::pair<int, int>> temp;

//i, j를 기준으로 해당하는 모든 테트로미노
void solution(int i, int j, int count, int sum)
{
	//성공조건
	if (count == 4)
	{
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < m; j++)
			{
				cout << check[i][j];
			}
			cout << "\n";
		}

		cout << "\n";
		if (value < sum)
		{
			value = sum;
		}
		cout << sum << endl;
		return;
	}

	int c = 0;
	for (int k = 0; k < 4; k++)
	{
		//범위탐색
		int y = i + yMove[k];
		int x = j + xMove[k];
		if ((0 <= x && x < m) && (0 <= y && y < n))
		{
			if (check[y][x] == false)
			{
				temp.push(std::pair<int, int>(y, x));
				c++;
			}
		}
	}

	for (int k = 0; k < c; k++)
	{
		auto v = temp.top();
		temp.pop();
		check[v.first][v.second] = true;
		solution(v.first, v.second, count + 1, sum + num[v.first][v.second]);
		check[v.first][v.second] = false;
	}
}

int main()
{
	cin >> n >> m;

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			cin >> num[i][j];
		}
	}

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			temp.push(std::pair<int, int>(i, j));
			check[i][j] = true;
			solution(i, j, 1, num[i][j]);
			check[i][j] = false;
		}
	}
	

	cout << value << endl;

	return 0;
}

하나씩 디버깅을 해보면서 틀린이유를 알아보니.. 

도형

위 도형의 모양이 절대 나올 수 없는 상황이였다...

왜 나올 수 없는 상황이였냐면 가정 자체부터 틀렸었다..

나는 가정을 DFS특성처럼 매개변수로 입력받은 하나의 도형을 기준으로 상하좌우를 탐색하여 경우의 수 라고 정의 하고 시작을 하였다.

하지만 위 방식대로 진행을 하면 절대 저 도형의 모양은 나올 수가 없다... 해서 방식을 달리해서 

Stack에 적재된 도형들을 기준으로 상하좌우 탐색을 하여 만들수 있는 모든 경우의 수 로 다시 정의했다.

탈출조건 : Stack의 크기가 4이면 합의 크기를 비교한다음 크면 저장.(위에서 정의한 것과 동일)

다음경우 :  Stack에 적재된 도형들을 기준으로 상하좌우 탐색루프를 돌면서 범위에 충족되면 재귀호출.

그래서 만들어진 코드는 아래와 같다. 

코드 : 

#include <iostream>
#include <stack>
#include <vector>
#include <limits>

using namespace std;

int N, M;
int num[500][500];
int mv[4][2] = { { -1, 0 }, { 1, 0 }, { 0, 1 }, { 0, -1 } };
bool check[500][500] = { false };
vector<std::pair<int, int>> temp;
int value = INT32_MIN;

void solution(int n, int m, int sum)
{
	//해당 정점 방문
	temp.push_back(std::pair<int, int>(n, m));
	check[n][m] = true;

	//탈출조건
	if (temp.size() == 4)
	{
		/*for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < M; j++)
			{
				cout << check[i][j];
			}
			cout << "\n";
		}*/

		if (value < sum)
		{
			value = sum;
		}
		return;
	}
	//다음경우
	int size = temp.size();
	for (int t = 0; t < size; t++) // 적재된 도형들을 기준
	{
		for (int i = 0; i < 4; i++)
		{
			int y = temp[t].first + mv[i][0];
			int x = temp[t].second + mv[i][1];
			if (check[y][x])
			{
				continue;
			}
			if ((0 <= y && y < N) && (0 <= x && x < M))
			{
				solution(y, x, sum + num[y][x]);
				temp.pop_back();
				check[y][x] = false;
			}
		}
	}
}
int main()
{
	cin >> N >> M;

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

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			solution(i, j, num[i][j]);
			check[i][j] = false;
			temp.pop_back();
		}
	}
	cout << value << endl;
	return 0;
}

처음엔 Stack을 사용하여 적재를 하였지만 vector를 사용하도록 변경하였다... 

Stack은 만들어진 자료구조 특성상 모든경우 접근이 불가능 하며, 맨 마지막에 넣은 데이터만 접근이 가능하도록 되어있기 때문이다.