[C++]백준15684번 사다리 조작

문제는 다음과 같다.

오늘은 백준15684번 사다리 조작 문제를 풀어보도록 하자. 사다리를 놓을 수 있는 경우의 수를 구한 후 1->1, 2->2… N->N까지 갈 수 있는 사다리의 최소 갯수를 찾는 문제이다.

조심해야할 점은 TLE 가 날 가능성이 매우 높다는 것이다. 만일 사다리의 갯수를 4개 이상 놨고, answer값을 갱신했다면 return해주는 백트래킹 과정을 꼭 해주어야한다. 그리고 더욱 큰 문제가 있다.

어떻게 사다리를 놓느냐는 것이다. 나의 경우에는 만약 1,1과 1,2가 이어져있다고 하면 ladder[1][2] = true로 해서 현재 지점과 왼쪽 지점을 이었다고 생각했다.

또한 고려해야할 점은 이중for문을 돌리는데 i=1, j=2부터 i=R, j=C까지 돌리면 TLE 에 걸린다는 것이다. 왜냐하면 세로지점을 중복탐색하기 때문에 세로지점은 매개변수로써 1을 받아서

i=row부터 i=R까지 처리해주어 중복을 줄여주었다.

                                     [코드]
#include <iostream>
#include <algorithm>
using namespace std;

int R, C, M, answer = 987654321;
bool ladder[32][11];

bool check_the_success(int i, int j) {
	for (int m = 1; m <= C; m++) {
		j = m;
		i = 1;
		while (1) {
			if (i == R + 1) {
				if (m != j) {
					return false;
				}
				break;
			}
			if (!ladder[i][j]) {
				if (ladder[i][j + 1]) {
					i++; j++;
				}
				else {
					i++;
				}
			}
			else {
				i++; j--;
			}
		}
	}
	return true;
}

void select_the_ladder(int row, int cnt) {
	if (cnt > 3)return;
	if (check_the_success(1, 1)) {
		answer = min(answer, cnt);
		return;
	}
	
	for (int i = row; i <= R; i++) {
		for (int j = 2; j <= C; j++) {
			if (!ladder[i][j] && !ladder[i][j-1]) {
				ladder[i][j] = true;
				select_the_ladder(i, cnt + 1);
				ladder[i][j] = false;
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> C >> M >> R;

	int col_dot, row_dot;
	for (int i = 0; i < M; i++) {
		cin >> row_dot >> col_dot;
		ladder[row_dot][col_dot + 1] = true;
	}

	select_the_ladder(1, 0);
	if (answer == 987654321)cout << -1;
	else cout << answer;
}