[BOJ 15684] 사다리 조작 (C++)

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

15684번: 사다리 조작

#include <iostream>
#include <vector>
#include <cstring>

#define MAX 987654321
using namespace std;

int N, M, H, a, b;
int ladder[32][12];
int ans = MAX;

bool isPossible() {
	for (int line = 1; line <= N; line++) {
		int start = line;
		int i = 1;
		while (i <= H) {
			if (ladder[i][line] == 1)
				line++;
			else if (ladder[i][line-1]==1)
				line--;
			i++;
		}
		if (start != line)
			return false;
	}
	return true;
}

void backtracking(int row, int num, int cnt) {
	if (num == cnt) {		//목표만큼 조작 완(목표: num)
		if (isPossible()) {
			ans = num;
			return;
		}
		return;
	}
	for (int i = row; i <= H; i++) {
		for (int j = 1; j <= N; j++) {
			if (ladder[i][j] == 0 && ladder[i][j - 1] == 0 && ladder[i][j + 1] == 0) {		//가능한 애들만 탐색
				ladder[i][j] = 1;
				backtracking(i, num, cnt + 1);
				ladder[i][j] = 0;
			}
		}
	}
}

int main() {
	memset(ladder, 0, sizeof(ladder));
	cin >> N >> M >> H;
	for (int i = 0; i < M; i++) {
		cin >> a >> b;
		ladder[a][b] = 1;
	}
	for (int i = 0; i <= 3; i++) {		//i: 조작하려는 사다리 수
		backtracking(1, i, 0);
		if (ans != MAX) 
			break;
	}
	if (ans != MAX) {
		cout << ans << "\n";
	}
	else {
		cout << -1 << "\n";
	}
	return 0;
}

고민하다가 힌트보고 풀었다.....

 

백트래킹 문제

 

1) 가로 사다리가 주어진 것을 좌표화 시키자. (a,b) 이면 a번째 가로선(행)에 b,b+1번째 세로선(열)에 사다리가 있는 것이다.

2) 3 이하의 사다리를 놓는 것만 허용한다고 했으므로, 각 갯수별(0개, 1개, 2개, 3개)로 백트래킹 탐색을 하고 답이 나왔을 경우(i 세로선의 결과가 i일 경우), 더이상 갯수별 백트래킹을 하지 않고 답을 리턴한다.

 

백트래킹 탐색 시 3개의 매개변수를 준다. (탐색하려는 가로선, 놓길 원하는 사다리의 갯수, 추가 완료한 사다리의 갯수)

cnt와 n이 같으면 완성된 모습이 답인지 체크한다.

이외의 경우, 해당 가로선부터 쭉 돌면서 가능한 애들인지 검사한 후 탐색한다.

가능한 애들인지, 즉 promising한지 체크하는 것은 현재 그 위치 앞, 뒤에 사다리가 있는지+그 위치에 사다리가 있는지를 체크한다. promising하면, ladder[해당위치]=1로 표시하고, cnt를 +1하고 다시 backtracking 한다.

 

답인지 체크하는 함수는 isPossible 함수로, 각 세로선 별로 체크한다. 가로선 1부터 시작하여, 가로선을 +1씩 증가시키면서 위치에 사다리가 있는지 체크한다. 여기서 주의할 점은 ladder[가로선][세로선-1] 까지 같이 체크해줘야 한다는 점이다.