사다리 조작 - 15684

문제 : https://www.acmicpc.net/problem/15684

15684번: 사다리 조작

코드 :

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

bool num[31][11] = { false };
int value = INT32_MAX;
int m, n, h = 0;

bool Check()
{
	for (int y = 1; y <= n; y++)
	{
		int temp = y;
		for (int x = 1; x <= h; x++)
		{
			if (num[x][temp]) temp += 1;
			else if (num[x][temp - 1]) temp -= 1;
		}

		if (temp != y)
			return false;
	}
	return true;
}

void solution(int x, int y, int count)
{
	//탈출조건
	if (count > 3)
	{
		return;
	}
	if (Check()) // 성공조건
	{
		if (value > count)
		{
			value = count;
		}
		return;
	}
	if (count == 3)
	{
		return;
	}

	//다음경우
	for (int i = x; i <= h; i++, y =1)
	{
		for (int j = y; j < n; j++)
		{
			if (num[i][j])
			{
				j++;
				continue;
			}
			num[i][j] = true;
			solution(i, j + 2, count + 1);
			num[i][j] = false;
		}
	}

}

int main()
{
	cin >> n >> m >> h;

	int x, y;
	for (int i = 0; i < m; i++)
	{
		cin >> x >> y;
		num[x][y] = true;
	}

	solution(1, 1, 0);
	if (value != INT32_MAX)
	{
		cout << value << "\n";
	}
	else
	{
		cout << -1 << "\n";
	}
	return 0;
}

이해하는데 상당히 오래걸린 문제.. 

주의사항 :

1. 인접으로 주어지는 가로선이 서로 연속할 수 없다는 것을 잊지말아야 한다.

2. 다음경우 구할때 y =1 을 해줘야 다음 가로선에서 처음부터 탐색을 한다. 

음.... 이 문제를 풀면서 재귀함수에도 두가지 패턴이 존재하는 것 같다. 

1. 재귀함수 안에 루프를 사용하여 완탐을 하는방법

2. 재귀함수만 사용하여 완탐을 하는 방법