사다리 조작 (feat.백준, 15684번)

사다리 조작
https://www.acmicpc.net/problem/15684

15684번: 사다리 조작

반응형

// woohyeon.kim
#include <cstdio>
using namespace std;
struct Position
{
	int x;
	int y;
};
int N, M, H;
int arr[31][11];
int result;

inline bool check()
{
	for (int iy = 0, check_x, check_y; iy < N; ++iy)
	{
		check_x = 0, check_y = iy;
		while (check_x < H)
		{
			if (arr[check_x][check_y] == 1)							++check_y;
			else if (check_y > 0 && arr[check_x][check_y - 1] == 1)	--check_y;
			++check_x;
		}
		if (iy != check_y)			return false;
	}
	return true;
}
void dfs(int index, int count)
{
	if (check())
	{
		if (result > count)		result = count;
		return;
	}
	if (count == 3)		return;
	for (auto ix = index; ix < H; ++ix)
		for (auto iy = 0; iy < N - 1; ++iy)
			if (arr[ix][iy] == 0 && arr[ix][iy + 1] == 0)
				arr[ix][iy] = 1, dfs(ix, count + 1), arr[ix][iy] = 0;
}
int main()
{
	scanf("%d%d%d", &N, &M, &H);
	for (auto ix = 0; ix < H; ++ix)
		for (auto iy = 0; iy < N; ++iy)
			arr[ix][iy] = 0;
	for (int ix = 0, x, y; ix < M; ++ix)
		scanf("%d%d", &x, &y), arr[x - 1][y - 1] = 1;

	result = 4;
	dfs(0, 0);
	if (result == 4)		printf("-1\n");
	else					printf("%d\n", result);
	return 0;
}
// *&)*@*

1. 사다리가 놓인 좌측의 위치를 1로 봅니다.
2. dfs로 사다리 설치시, 현재 나의 위치와 내 우측의 위치가 모두 사다리가 없는지를 확인합니다.
3. 설치가 될때마다 check를 통해 출발y부터 도착y가 같은지를 보고, 다르면 바로 리턴합니다.

​

9% 시간 초과때문에 시간이 제법걸렸습니다.