BOJ 15684: 사다리 조작

#BOJ 15684: 사다리 조작

15684번: 사다리 조작

#풀이

문제를 보고 저번에 푼 연구소 문제와 비슷하다고 생각이 들었다.

 

누가봐도 백트래킹을 사용해서 조건에 맞게 사다리를 만들었는지 확인 하는 문제다.

 

다른 사람들은 dfs를 사용해서 푼 사람들이 많았지만 난 그냥 평소에 백트래킹 푸는 것처럼 재귀를 활용하여 풀었다.

 

근데 시간초과가 떴다......

 

그 이유는 굳이 만들지 않아도 되는 사다리를 만들어서 시간초과가 나온 것이 었다.

 

1번 사다리는 1번 으로 가야 한다.

 

이 뜻은 사다리가 짝수개로 있어야 한다.  가로선을 타고 2번으로 나갔으면 2번에서 1번으로 가로 선을 타고 들어와야한다.

여기서 간과한 것이 들어오는 사다리의 높이는 상관이 없다. (항상 내려오므로) 

 

나는 처음에 똑같은 결과를 반복적으로 얻어왔던 것이다.

 

이것을 해결하는 것이 반복문 안에 있는 while(!arr[i][j-1]&& !arr[i][j+1]) i++; 이다.

 

저 코드로 인해 가장 아래 단에 있는 사다리를 구하여 해결 하였다.

 

 

#풀이

#include<iostream>

using namespace std;
int n, m, h;
int arr[272][11];
int ans = 0x7f7f7f7f;
bool func() {

	for (int i = 1; i <= n; i++) {
		int idx = i;
		for (int j = 1; j <= h; j++) {
			if (arr[j][idx] == 1)
				idx++;
			else if (arr[j][idx - 1] == 1)
				idx--;
		}
		if (i != idx) return 0;
	}

	return 1;
}

void solved(int cur) {
	if (cur > 3)
		return;
	if (func()) {
		ans = ans > cur ? cur : ans;
		return;
	}

	for (int j = 1; j < n; j++) {
		for (int i = 1; i <= h; i++) {
			if (arr[i][j] == 1) continue;

			if (arr[i][j - 1] == 1) continue;

			if (arr[i][j + 1] == 1) continue;

			arr[i][j] = 1;
			solved(cur + 1);
			arr[i][j] = 0;
			while (!arr[i][j - 1] && !arr[i][j + 1]) i++;
		}
	}
}


int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m >> h;
	for (int i = 1; i <= m; i++) {
		int a, b;
		cin >> a >> b;
		arr[a][b] = 1;
	}
	solved(0);

	ans = ans == 0x7f7f7f7f ? -1 : ans;
	cout << ans << '\n';
	return 0;
}