[백준/BOJ] 백준 15684번 : 사다리 조작

www.acmicpc.net/problem/15684

15684번: 사다리 조작

가로선을 선택하는 함수와, i번 세로선의 결과가 i번이 나오는지 확인하는 함수를 만든다. 사다리는 int row[31][11]로 표시한다. 가로선을 놓을 수 있는 위치마다 번호를 매겨 다음에 선택할수 있는 가로선은 이전에 선택한 가로선 이후 것들이 되도록 한다.

 

코드

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

int n, m, h;
int row[31][11];

void Pre()
{
	for (int i = 0; i < 31; i++)
		for (int j = 0; j < 11; j++)
			row[i][j] = 0;
}

//i번 세로선의 결과가 i번이 나오는지 확인
bool Check()
{
	for (int i = 1; i <= n; i++)
	{
		int here = i; //i번 세로열
		
		//사다리 아래로 내려가기
		for (int j = 1; j <= h; j++)
		{
			//오른쪽으로 이동
			if (here != n && row[j][here] == 1)
				here++;

			//왼쪽으로 이동
			else if (here != 1 && row[j][here - 1] == 1)
				here--;
		}

		//i번 세로선의 결과가 i번이 아닐때
		if (here != i)
			return false;
	}

	return true;
}

int Solve(int add_num, int last_selected)
{
	//가로선 개수가 3개를 넘을때
	if (add_num > 3)
		return 987654321;

	//i번 세로선의 결과가 i번이 나올때
	if (Check())
		return add_num;

	int ret = 987654321;

	//다음에 선택할수 있는 가로선은 이전에 선택한 가로선 이후것들이다
	int can_selected = last_selected + 1;

	//고를 수 있는 가로선이 없을때
	if (can_selected > (n - 1)*h)
		return 987654321;

	for (int i = can_selected / (n - 1) + 1; i <= h; i++)
		for (int j = can_selected % (n - 1); j <= n - 1; j++)
		{
			//해당 위치에 가로선이 없을때
			if (row[i][j] == 0)
			{
				int this_selected = (i - 1)*(n - 1) + j;

				//해당 위치 선택시 가로선이 연속하는지 확인
				if (j != 1 && row[i][j - 1] == 1)
					continue;
				if (j != n - 1 && row[i][j + 1] == 1)
					continue;

				row[i][j] = 1; //가로선 선택
				ret = min(ret, Solve(add_num + 1, this_selected));
				row[i][j] = 0; //가로선 선택 해제
			}

		}

	return ret;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	int a, b;
	int result;

	cin >> n >> m >> h;

	Pre();

	for (int i = 0; i < m; i++)
	{
		cin >> a >> b;
		row[a][b] = 1; //a번 점선, b,b+1번 세로선으로 가로선 표시
	}

	result = Solve(0, 0);

	if (result == 987654321)
		cout << -1;
	else
		cout << result;

	return 0;
}