[BOJ] 15684 : 사다리 조작 - travelbeeee

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

---

[ 알고리즘풀이 ]

 기존의 삼성 기출 문제처럼 모든 경우에 대해서 Backtracking을 통해 사다리를 조작하면 시간초과에 걸리게 되는 문제다. 

 

정의

ladder[a][b] : a번 가로선에서 b ~ b + 1 번 새로 선에 사다리가 연결되어있으면 1, 아니면 0.

 

1. 사다리를 우리는 최대 3개까지 조작할 수 있으므로, 0개부터 3개까지 조작하는 수를 하나씩 늘려가며 Backtracking 을 통해 조작하는 경우의 수를 구한다.

 ( 이때, 앞에서 조작으로 답이 갱신되었다면, 조작하는 수를 늘려가는 것은 의미가 없으므로 게임을 종료한다. )

 

2. Backtracking 을 통해 조작할 사다리를 정해야 한다. 이때, ladder[a][b] 에 사다리를 연결하려면, ladder[a][b - 1], ladder[a][b], ladder[a][b + 1] 이 모두 사다리가 없어야만 한다. 또, i번 가로선에서 사다리를 조작했다면, 그다음 조작할 사다리는 i번 가로선부터 다시 찾아가면 되므로 ( 즉, i번 보다 작은 쪽에서 사다리를 조작하는 경우는 이미 앞의 Backtracking 을 통해 계산하였으므로 ) Backtracking 인자에는 가로선 i 와 내가 조작할 사다리의 개수, 조작한 사다리의 개수를 인자로 넘겨준다.

 

3. 조작할 사다리의 개수와 조작한 사다리의 개수가 같다면 사다리 게임을 진행해 i번 째 사다리가 i 번에서 끝나는지 check 한다.

 

# 2번 과정에서 가로선을 인자로 넘겨주지 않고, 사다리를 다시 처음부터 순회하며 Backtracking을 진행해 시간 초과를 받았다.

 

#include<iostream>
#include<algorithm>
#include<vector>

#define INF 987654321
using namespace std;

int N, M, H, a, b, ans = 987654321;
bool ladder[31][11];

bool checkGame() {
	for (int k = 1; k <= N; k++) {
		int i = 1, j = k;
		while (i <= H) {
			if (ladder[i][j])
				j++;
			else if (ladder[i][j - 1])
				j--;
			i++;
		}
		if (j != k)
			return false;
	}
	return true;
}

void Backtracking(int row, int goal, int cnt) {
	if (ans != INF)
		return;

	if (goal == cnt){
		if (checkGame())
			ans = goal;
		return;
	}

	for (int i = row; i <= H; i++) {
		for (int j = 1; j < N; j++) {
			if (ladder[i][j - 1] == 0 && ladder[i][j] == 0 && ladder[i][j + 1] == 0) {
				ladder[i][j] = 1;
				Backtracking(i, goal, cnt + 1);
				ladder[i][j] = 0;
			}
		}
	}
	return;
}

void Init(void) {
	for (int i = 0; i <= 3; i++) {
		if (ans != INF)
			break;
		Backtracking(1, i, 0);
	}
}

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

	cin >> N >> M >> H;
	for (int i = 0; i < M; i++) {
		cin >> a >> b;
		ladder[a][b] = 1;
	}

	Init();

	if (ans == INF)
		ans = -1;
	cout << ans;
}

---