인프런 커뮤니티 질문&답변

왜 틀렸는지 도저히 모르겠습니다..

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

const int dy[2] = { 0,0 };
const int dx[2] = { -1, 1 };

int N, M, H, a, b, adj[31][21], visited[31][21], ret[21], cnt;
bool isOk;

void Print()
{
	cout << endl;
	for (int y = 0; y < 31; y++)
	{
		for (int x = 0; x < 21; x++)
			cout << adj[y][x];
		cout << endl;
	}
	cout << endl;
}

void Move(int y, int x, int start)
{
	if (y == H + 1)
	{
		ret[start] = x;
		return;
	}

	bool isDown = true;

	visited[y][x] = start;

	// 좌우 확인
	for (int i = 0; i < 2; i++)
	{
		int ny = y;
		int nx = x + dx[i];

		if (ny > H + 1 || nx <= 0 || nx > 2 * N - 1)
			continue;
		if (visited[ny][nx] == start)
			continue;
		if (adj[ny][nx] == 0)
			continue;

		Move(ny, nx, start);
		isDown = false;
	}

	if (isDown)
		Move(y + 1, x, start);
}

bool Check()
{
	// 값들 초기화
	memset(ret, 0, sizeof(ret));
	memset(visited, 0, sizeof(visited));

	for (int x = 1; x <= N; x++)
	{
		Move(0, x * 2 - 1, x * 2 - 1);
		if (ret[x * 2 - 1] != x * 2 - 1)
		{
			return false;
		}
	}

	return true;
}

void AddLadder()
{
	if (isOk)
		return;

	if (cnt >= 3)
		return;

	for (int y = 1; y <= H; y++)
		for (int x = 1; x < N; x++)
		{
			if (adj[y][x * 2] != 1 && adj[y][x * 2 - 2] != 1 && adj[y][x * 2 + 2] != 1)
			{
				adj[y][x * 2] = 1;
				cnt++;

				if (Check())
				{
					isOk = true;
					// Print();
					return;
				}
				AddLadder();

				adj[y][x * 2] = 0;
				cnt--;
			}
		}

	return;
}


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

	// 사다리 초기값
	for (int y = 0; y <= H + 1; y++)
		for (int x = 1; x <= N; x++)
			adj[y][x * 2 - 1] = 1;

	// 가로선 정보
	for (int i = 0; i < M; i++)
	{
		cin >> a >> b;
		adj[a][b * 2] = 1;
	}

	if (Check())
		cout << 0;
	else
	{
		AddLadder();
		if (cnt == 0)
			cout << -1;
		else
			cout << cnt;
	}

	return 0;
}