[DFS 백트래킹] 백준 15684 사다리 조작 C++

 

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

#include <iostream>
#include <vector>

using namespace std;

int n, m, h;
int ans = 4;
vector<vector<int>> v;

bool check()
{
	for (int i = 1; i <= n; i++)
	{
		int temp = i;
		for (int j = 1; j <= h; j++)
		{
			if (v[j][temp] == 1) temp++;
			else if (v[j][temp - 1] == 1) temp--;
		}
		if (temp != i) return false;
	}

	return true;
}

void dfs(int x, int y, int depth)
{
	if (check() == true)
	{
		ans = min(ans, depth);
		return;
	}

	if (ans <= depth) return;
	if (depth == 3) return;

	for (int i = y; i <= h; i++) // DFS 안에 for문 위치
	{
		for (int j = x; j <= n; j++)
		{
			if ((v[i][j] == 0) && (v[i][j - 1] == 0) && (v[i][j + 1] == 0))
			{
				v[i][j] = 1;
				dfs(j, i, depth + 1);
				v[i][j] = 0;
			}
		}
		x = 1;
	}
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	cin >> n >> m >> h;
	v.resize(h + 2, vector<int>(n + 2, 0));
	
	for (int i = 0; i < m; i++)
	{
		int a, b;
		cin >> a >> b;
		v[a][b] = 1;
	}

	dfs(1, 1, 0);

	if (ans == 4)
	{
		cout << -1;
	}
	else
	{
		cout << ans;
	}
}