백준 15684 사다리 조작 c++

문제 설명

입력으로 a, b가 들어오는데, b와 b+1을 잇는 사다리가 a에 있다는 의미

위에 그림으로 보면 2, 3이면 3과 4사이를 잇는 2 위치에 사다리가 있다는 의미임

가로선을 최소로 추가해서 i번 세로선의 결과를 i로 만드는 문제

 

세로선의 개수는 2<=n<=10이고

세로선마다 가로선을 놓을 수 있는 위치의 개수는 1<=h<=30

즉, 가로선의 개수는 0<=m<=(n-1)*h만큼이 가능하다

최대 수를 넣어보면 270개의 경우의 수가 있다

 

특이점으로, 가로선은 3개까지 추가할 수 있다. 정답이 3보다 크면 -1, 불가능해도 -1이다

 

정리하면, (n-1)*h개 중에서 3개를 고르는 경우의 수가 되고,

최대 수로 치면 9*30중에 3개를 고르는 것이니까 270^3이 된다

 

그렇게 큰 수가 아니므로 전체 다 돌려보면 되고, 브루트포스 문제가 된다

 

 

전체 코드

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
int n, m, h;
bool map[31][11];
int res = 1e9;

bool chk_game() {
	for (int i = 1;i <= n;i++) {
		int now = i; //row
		for (int j = 0;j < h;j++) { //모든 높이에서 사다리 설치해 봄
			if (map[j][now]) {
				//오른쪽으로
				now += 1;
			}
			else if (map[j][now - 1]) {
				//왼쪽으로
				now -= 1;
			}
		}
		if (now != i) return false; //i가 아니면 이건 아님
	}
	return true; //찾음
}

void go(int y, int cnt) {
	if (cnt >= 4) return; //추가된 가로선 3개 넘으면 -1
	if (chk_game()) {
		res = min(res, cnt);
		return;
	}
	for (int i = y; i <= h;i++) {
		for (int j = 1;j < n;j++) {
			//가로선이 연속하거나 겹치면 안 된다
			if (!map[i][j] && !map[i][j - 1] && !map[i][j + 1]) {
				map[i][j] = true;
				go(i, cnt+1);
				map[i][j] = false; //백트래킹
			}
		}
	}
	return;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie();
	cin >> n >> m >> h;
	for (int i = 0;i < m;i++) {
		int y, x;
		cin >> y >> x;
		map[y - 1][x] = true; //y-1번째 col에서 x~x+1을 잇는 사다리
	}
	
	go(0, 0);
	if (res == 1e9) cout << -1;
	else cout << res;
}

 

코드 설명

처음에 입력 받으면서 들어오는 사다리를 map에 넣어준다

 

가로선은 3개까지만 가능하다

정답이 가능하면 최소를 비교하고 반환한다

그렇지 않다면 탐색을 또 가는데, 여기서 중요한 건 가로선이 연속으로 놓이거나 겹치면 안 된다

왼쪽, 오른쪽에 연속으로 놓일 수 있고, 겹칠 수 있으니까 각 경우를 예외로 두고, 재귀를 돌린다

다른 경우도 백트래킹하기 위해서 false로 돌려놓는다

정답을 찾는 부분은 n부터 h까지 모든 경우를 보면서 사다리를 설치한다

어떤 위치에서 왼쪽 오른쪽을 보고 i가 i에 넣어졌는지 확인한다