알고스팟 게임판 덮기

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

algospot.com :: BOARDCOVER

 

전형적인 완전탐색 문제였다.

 

 

 

접근방법

1. 2차원 배열에서 한 칸씩 이동한다.

2. 이때 가능한 모든 경우에 대해 블록을 놓는다.(가능한 경우의 수는 밑에 참고)

3. 2차원 배열의 끝에 도달했을 때, 카운팅을 해준다.

 

2. 가능한 경우의 수

 

ㅁ ㅁ

ㅁ

 

ㅁ ㅁ

    ㅁ

 

ㅁ

ㅁ ㅁ

 

    ㅁ

ㅁ ㅁ

 

 

 

 

시간 복잡도

흰 칸의 수 = 50 이고

놓을 수 있는 블록의 수 = 50/3 = 16 이다.

그럼 총 경우의 수는 4^16 = 2^23 이다.

이때, 블록의 모양때문에 많은 경우가 걸러진다.

따라서 시간 안에 가능하다.

 

 

 

 

코드

#include <iostream>
#include <algorithm>
#include <memory.h>
using namespace std;

int tc, h, w;
char map[21][21];
int visit[21][21];
int dy1[4] = { 0, 1, 0, 1};
int dx1[4] = { 1, 0, 1, 0};
int dy2[4] = {1, 1, 1, 1};
int dx2[4] = {0, -1, 1, 1};
int tar, res;

void recur(int p, int cnt) {
	int y = p / w;
	int x = p % w;

	if (p == h * w) {
		if(tar == cnt) res++;
		return;
	}

	if (visit[y][x] == 1 || map[y][x] == '#') {
		recur(p + 1, cnt);
		return;
	}

	for (int i = 0; i < 4; i++) {
		int ty1 = y + dy1[i];
		int tx1 = x + dx1[i];
		int ty2 = y + dy2[i];
		int tx2 = x + dx2[i];

		//범위 체크
		if (ty1 < 0 || ty1 >= h || tx1 < 0 || tx1 >= w) continue;
		if (ty2 < 0 || ty2 >= h || tx2 < 0 || tx2 >= w) continue;
		//모양 들어갈 수 있는지 체크
		if (visit[ty1][tx1] == 1 || visit[ty2][tx2] == 1) continue;
		if (map[ty1][tx1] == '#' || map[ty2][tx2] == '#') continue;

		visit[ty1][tx1] = visit[ty2][tx2] = visit[y][x] = 1;
		recur(p+1, cnt+1);
		visit[ty1][tx1] = visit[ty2][tx2] = visit[y][x] = 0;
	}
}

int main() {
	scanf("%d", &tc);
	while (tc--) {
		memset(visit, 0, sizeof(visit));
		tar = 0; res = 0;

		scanf("%d %d", &h, &w);
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				scanf(" %c", &map[i][j]);
				if (map[i][j] == '.') tar++;
			}
		}

		if (tar % 3 == 0) {
			tar /= 3;
			recur(0, 0);
			printf("%d\n", res);
		}
		else {
			printf("0\n");
		}
	}
	return 0;
}

 

 

 

 

실수

예전에 비슷한 문제를 풀어서 접근은 맞았다.(왼쪽상단부터 시작하여 한 칸씩 전진하는 것)

하지만 그렇게 접근하는 이유에 대해서 정확히 알지 못했다.(중복 방지)

또 블록의 모양을 틀리게 생각했다. 그래서 답을 내기까지 시간소요가 있었다.

알고리즘에 대한 논리적 근거와 검산을 위한 확실한 시뮬레이션이 필요함을 느꼈다.