[BOJ]백준 15684번: 사다리 조작/Backtracking

www.acmicpc.net/problem/15684

15684번: 사다리 조작

삼성 A형 기출인 사다리 조작 문제

시간을 줄일 수 있는 분기가 많기에 백트래킹 연습에 좋은 문제라고 생각한다.

 

사다리는 0개~3개를 설치할 수 있다.

따라서 4번의 반복문을 통해 해당 탐색에서 놓을 총 사다리 수를 정하고 백트래킹 루틴을 돌려 주었다.

까다로웠던 점은 해당 stage에 사다리 설치를 완료한 뒤 중복 체크를 막기 위한 다음 stage 선정이 조금 어려웠다.

그래서 처음엔 행 - 열 순서로 검사하되 특정 좌표에 사다리를 설치했다면 이전 행은 검사하지 않도록 구현해주었었다.

 

하지만 recursion tree를 간소화시킬 수 있는 더 좋은 솔루션이 있었다.

문제에서는 사다리를 좌표화해서 제공했고, 점선 또한 그림에 전부 표시되어 있기 때문에 모든 빈칸에 대해 다 검사해야 할 것 같은 착각(?)이 들 수 밖에 없었다.

 

하지만 점선을 제외하고 기존에 설치된 사다리에서 새로 사다리를 추가해야 하는 상황을 가정해보면

왼쪽 경우(빨간 사다리 설치)와 오른쪽 경우(파란 사다리 설치)는 완전히 같은 경우라고 볼 수 있다.

왜냐면 사다리의 위치를 내리던 올리던 다른 사다리의 상태에는 영향을 주지 않기 때문이다(같은 스터디원분께서 괄호 체크와 비슷한 원리라고 말씀해주셨다). 

따라서 stage에서 사다리를 한 번 설치하고 나면, 이후에 이미 설치된 사다리가 나올 때 까지의 빈칸은 고려해줄 필요가 없다.

코드에서의 while(i<h) 구문이 해당 코드이다.

이러한 루틴을 추가해주고 나서 시간이 548ms -> 0ms로 감소했다.

#include <cstdio>
int n, m, h, ans = 5;
bool map[31][11];
bool ladder() {
	for (int j = 1; j <= n; j++) {
		int cur = j;
		for (int i = 1; i <= h; i++) {
			if (cur && map[i][cur - 1])cur--;
			else if (map[i][cur])cur++;
		}
		if (cur != j)return false;
	}
	return true;
}
void dfs(int dep, int k) {
	if (ans != 5)return;
	if (dep > k) {
		if (ladder())ans = k;
		return;
	}
	for (int j = 1; j < n; j++)
		for (int i = 1; i <= h; i++) {
			if (map[i][j] || map[i][j - 1] || map[i][j + 1]) continue;
			map[i][j] = 1;
			dfs(dep + 1,k);
			map[i][j] = 0;
			while (i < h) {
				if (map[i][j - 1] || map[i][j + 1])break;
				i++;
			}
		}
	return;
}
int main() {
	scanf("%d%d%d", &n, &m, &h);
	for (int j = 0, a, b; j < m; j++) {
		scanf("%d%d", &a, &b);
		map[a][b] = 1;
	}
	for (int i = 0; i < 4; i++) {
		dfs(1, i);
		if (ans != 5) {
			printf("%d", ans);
			return 0;
		}
	}
	printf("-1");
	return 0;
}

어렵지만 생각할 거리가 많았던 좋은 문제