[백준 15684] 사다리 조작

문제 바로가기

15684번: 사다리 조작

 

 

위의 그림과 같은 사다리가 주어졌을 때,

i번째 선이 i번째로 나오게 하는 최소한의 사다리 개수를 출력하는 문제이다.

 

사다리를 0개부터 3개까지 놓을 수 있기 때문에 사다리를 늘려가면서

놓을 수 있는 모든 경우의 수를 계산해야한다.

사다리를 놓는 부분은 백트래킹으로 구현하였다.

 

solve() 함수 내에서

for (int i = 1; i <= H; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			if (!ladder[i][j])
			{
				if (ladder[i][j - 1] == 1 || ladder[i][j + 1] == 1)
					continue;
				ladder[i][j] = 1;
				solve(digit + 1, end_digit);
				copy_ladder(tmp_ladder, ladder);
			}
		}
	}

 

사다리 가로선을 보는 부분에서 사다리를 놓은 이후부터 보면되는데 계속 1번째부터 봐줘서 시간초과가 떴다.

전 문제도 똑같은 실수 했는데,,

조 심 합 시 다

 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int N, M, H;
int ladder[31][11]; //H, N
int min_ladder = -1;

bool check_each_ladder(int l) {
	int start = 0;
	int next = l;

	for (int i = start + 1; i <= H; i++)
	{
		if (ladder[i][next - 1] == 1)
		{
			start = i;
			next--;
		}
		else if (ladder[i][next] == 1)
		{
			start = i;
			next++;
		}
	}

	if (next == l)
		return true;
	return false;

}

bool check_all_ladder() {
	for (int i = 1; i <= N; i++)
	{
		if (!check_each_ladder(i))
			return false;
	}

	return true;
}

void copy_ladder(int orig[][11], int neww[][11])
{
	for (int i = 1; i <= H; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			neww[i][j] = orig[i][j];
		}
	}
}

void solve(int digit, int end_digit, int ni)
{
	if (digit == end_digit)
	{
		if (check_all_ladder()) {
			min_ladder = digit;
		}
		return;
	}
	int tmp_ladder[31][11];
	copy_ladder(ladder, tmp_ladder);

	for (int i = ni; i <= H; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			if (!ladder[i][j])
			{
				if (ladder[i][j - 1] == 1 || ladder[i][j + 1] == 1)
					continue;
				ladder[i][j] = 1;
				solve(digit + 1, end_digit, i);
				copy_ladder(tmp_ladder, ladder);
			}
		}
	}
}

int main()
{
	cin >> N >> M >> H;

	for (int i = 0; i < M; i++)
	{
		int a, b;
		cin >> a >> b;
		ladder[a][b] = 1;
	}

	N--;

	for (int i = 0; i <= 3; i++)
	{
		solve(0, i, 1);
		if (min_ladder != -1) {
			break;
		}
	}

	cout << min_ladder << endl;

	return 0;
}