[백준/15684] 사다리 조작 (C++)

문제 해석

누군가 백트래킹을 시도할 때에는, 조건을 잘못 주면 개망한다고 했다. 내가 그랬다.

이 문제를 풀기 위해서 2일의 시간이 걸렸고, 백준에 40번을 제출했는데 다 틀렸다.

현자타임이 온다. 내가 이것밖에 안되나 싶다.

결국 다른 사람이 작성한 코드를 봤는데도 이해가 잘 안됐다. 허무하다.

 

구현

#include <cstdio>

using namespace std;

bool ropes[31][11] = { 0 };
int N, H, M;
int answer = 4;

bool check()
{
	for (int i = 1; i <= N; i++)
	{
		int loc = i;

		for (int j = 1; j <= H; j++)
		{
			if (ropes[j][loc] == 1)
			{
				loc++;
			}
			else if (loc > 1 && ropes[j][loc - 1] == 1)
			{
				loc--;
			}
		}

		if (loc != i) return false;
	}
	return true;
}

void recur(int x, int cnt, int y)
{
	if (cnt >= answer) return;

	if (check())
	{
		if (answer > cnt) answer = cnt;
		return;
	}

	if (cnt == 3) return;

	for (int i = x; i <= H; i++, y = 0)
	{
		for (int j = y; j < N; j++)
		{
			if (ropes[i][j]) j++;
			else if (ropes[i][j - 1] == 0 && ropes[i][j + 1] == 0)
			{
				ropes[i][j] = 1;
				recur(i, cnt + 1, j + 2);
				ropes[i][j] = 0;
			}
		}
	}
}

int main(void)
{
	scanf("%d %d %d", &N, &M, &H);

	for (int i = 0; i < M; i++)
	{
		int link, rope;
		scanf("%d %d", &link, &rope);

		ropes[link][rope] = 1;
	}

	recur(1, 0, 1);

	if (answer == 4) printf("-1\n");
	else printf("%d\n", answer);

	return 0;
}