알고스팟_ 게임판 덮기

2020-04-21 · 배운 것 · 5분 읽기

https://www.algospot.com/judge/problem/read/BOARDCOVER

algospot.com ::
BOARDCOVER

풀이방법

첫번째 풀이

그냥 그 점에 대한 블록이 가질수 있는 12가지 형태를 모두 선택하는 방법을 사용했었다.

하지만 이렇게 풀게되면 시간도 ( 12^(50/3) = 184,884,258,895,036,416‬ ) x (테스트케이스 수) 말도 안되는데다가 중복으로 세는 경우도 있어 더 보완할 필요성이 있다.

두번째 풀이

생각해보면 항상 맨위쪽에서 맨 좌측의 경우의 점을 골라 블록이 대응하는지 살펴볼텐데, 이를 이용하면

가능한 경우는 12에서 4가지로 줄어든다. ( 조금만 생각해보면 당연하다 )
그러면 시간은 (4 ^ (50/3) ) x(테스트 케이스 수) = 128,849,018,880 이렇게 되는데 여전히 크긴하다.. ㅋㅋㅋ
하지만, 저 네가지 경우가 다 배치될 확률은 거의 없고 한 1 ~2가지 정도 배치될테니 약 (2^ (50/3)) x(테스트 케이스 수) = 1,966,080‬ 이므로 무난히 통과 가능할것이다.
그러니 시간제한인 2초안에는 무조건 들어갈거라고 생각할수있다.

전체코드

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

vector<vector<int>>dy = { {0, 0, 1}, {0, 1, 1},{0, 1, 1},{0, 0, 1}};
vector<vector<int>>dx = { {0, 1, 1}, {0, 0, -1},{0, 0, 1},{0, 1, 0}};

vector<vector<char>> originalMap;
int N, M;
int emptyPlace;

void Input()
{
	cin >> N >> M;
	originalMap.resize(N+2);
	for (int i = 0; i < N; i++)
		originalMap[i].resize(M + 2);

	emptyPlace = 0;
	char value;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			cin >> value;
			originalMap[i][j] = value;
			if (value == '.')
				emptyPlace++;
		}
	}
}

bool inRange(int y, int x)
{
	if (y >= 0 && x >= 0 && y < N && x < M)
		return true;
	return false;
}

pair<int, int>findNextPoint(const vector<vector<char>>& map)
{
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
			if (map[i][j] == '.')
				return { i, j };
	return { -1, -1 };
}

int dfs(int y, int x, int dir, int cnt, vector<vector<char>>map)
{
	//기저 사례 : 남은 공간을 블록의 넓이로 나눴을때 나누어떨어지지 않으면 당연히 채울수 없음은 자명함.
	if (emptyPlace % 3 != 0)
		return 0;

	//채우기
	for (int i = 0; i < 3; i++)
	{
		int ny = y + dy[dir][i];
		int nx = x + dx[dir][i];

		//범위가 넘었으면 return 0
		if (inRange(ny, nx) == false)
			return 0;

		//이미 자리가 있으면 return 0
		if (map[ny][nx] != '.')
			return 0;

		map[ny][nx] = '#';
	}

	//탈출조건 : cnt가 이때까지 문제없이 왔다면 전체 공간을 다 채웠음은 당연함.
	if ((emptyPlace / 3) == cnt)
		return 1;

	int ret = 0;

	//다음거 물색
	pair<int, int> nextPos = findNextPoint(map);
	for (int i = 0; i < 4; i++)
	{
		ret += dfs(nextPos.first, nextPos.second, i, cnt+1, map);
	}
	return ret;
}

int main()
{
	int t;
	cin >> t;
	for (int i = 0; i < t; i++)
	{
		Input();
		auto firstPos = findNextPoint(originalMap);
		int ans = 0;
		for(int i =0; i<4; i++)
			ans += dfs(firstPos.first, firstPos.second,i, 1, originalMap);
		cout << ans << endl;
	}

	return 0;
}

후기

종만북 코드가 더 깔끔하네..

종만북처럼 맵을 복사하는게 아니고 블록을 넣었다 뺐다 하는식으로 짜면 훨씬 좋을것같다.