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

[백준 15684번]
https://www.acmicpc.net/problem/15684

삼성기출의 특징을 잘 보여주는 문제인 것 같다. DFS를 이용한 백트래킹 구현 문제로 아이디어는 간단했다. 다만, 시간 제한은 너그럽게 줘서 한 번에 풀 수 있었고, 시간 제한이 빡빡했다면 어려웠을 것 같다.

풀이

1.

DFS로 사다리를 놓을 수 있는 공간을 하나씩 찾아가면서 최대 개수인 3개에 도달했을 때도 조작이 완료되지 않으면 -1을 출력하면 된다.

사다리를 새로 놓는 곳의 좌표를 (r,c)라고 하면

이런 식으로 하나씩 새로 놓아가면서 백트래킹을 DFS로 구현하면 된다.

2.

다만 여기서 함정이 하나 존재한다. 주어지는 입력의 개수를 보면 사다리를 최대 300개를 놓을 수 있고, 그걸 3번의 완전탐색을 하게 되면 경우의 수가 엄청나게 많아진다.

이 문제에서 핵심은 경우의 수를 줄이는 백트래킹을 구현하는 것이다. 필자는 완전탐색으로 착각하여 모든 경우의 수를 탐색하는 구현으로 처음에 코드를 짜서 제출했다. 다행히 시간제한이 넉넉하여 통과는 했지만 1600ms라는 너무 느린 결과를 얻게 되었다.

문제를 다시 한 번 생각해보면, 최대로 놓을 수 있는 사다리의 개수를 0부터 3까지 증가시키면서 최대 사다리 개수와 일치하는 값을 찾게 되면 나머지 경우의 수는 탐색할 필요가 없다(사다리의 최대 개수가 0부터 시작하기 때문에 0일 때, 조작이 완료되는 경우가 등장하면 그 이후의 경우의 수는 상관이 없기 때문이다).

따라서 for문으로 사다리의 최대 개수를 0부터 3까지 순회하면서 dfs를 통한 백트래킹을 수행하면 0ms만에 문제를 맞힐 수 있게 된다.

C++ 코드

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <utility>  // pair
#include <tuple>
#include <stack>
#define ll long long
#define INF 1e9
using namespace std;

int ans = 987654321;
int ladder[31][11];  // ladder[h][n]
int n,m,h;

bool isManipulated() {
	for(int j=1;j<=n;++j) {
		int col = j;
		for(int i=1;i<=h;++i) {
			if(ladder[i][col]) col++;  // starting point, goes right
			else if(ladder[i][col-1]) col--;  // ending point, goes left

			// nothing happens, goes down
		}

		if(col != j) {
			return false;
		}
	}

	return true;
}

void dfs(int maxDepth,int cnt) {
	if(maxDepth == cnt) {
		if(isManipulated()) {
			printf("%d\n", maxDepth);  // 현재의 maxDepth에서는 최대값이자, 남은 maxDepth 후보 중에서는 최소값.
			// maxDepth가 0부터 시작하기 때문에 결국 최소값이 된다
			exit(0);
		}

		return;
	}

	for(int j=1;j<n;++j) {
		for(int i=1;i<=h;++i) {
			if(ladder[i][j] || ladder[i][j-1] || ladder[i][j+1]) continue;
			ladder[i][j] = 1;
			dfs(maxDepth,cnt+1);
			ladder[i][j] = 0;

			while(!ladder[i][j-1] && !ladder[i][j+1]) i++;  // skip rows until we can put a ladder
		}
	}

	return;
}


int main(void) {
	// ios_base :: sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

	scanf("%d%d%d", &n,&m,&h);
	for(int i=1;i<=m;++i) {
		int a,b;
		scanf("%d%d", &a, &b);

		ladder[a][b] = 1;
	}

	for(int i=0;i<4;++i) {
		dfs(i,0);
	}
	if(ans==987654321)
		ans = -1;

	printf("%d\n", ans);
	
	return 0;
}