백준 15684 (사다리 조작)

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

15684번: 사다리 조작

해당 문제는 사다리를 최대 3개 까지 놓을 수 있으므로 재귀를 통한 완전탐색을 이용하여 문제를 해결 할 수 있다.

풀이

사다리를 두는 순서는 상관 없음으로 조합을 이용하여 재귀 호출을 사용하며 이때 사다리를 놓는 곳은 1, 사다리의 왼쪽에 해당하는 영역은 2로 Check를 실시한다. 따라서 1인 경우에는 X좌표를 +1 하는 것으로 우측으로 이동하며 만약 2인 경우에는 X좌표를 -1 하며 좌측으로 이동한다.

 

#include <iostream>
#include <cstring>

using namespace std;
int map[32][12];
int my, mx;
int h;
int minn = 10000;

bool check(){
	int visit[32][12] = {0};
	int cpvisit[32][12] = { 0 };

	for (int x = 0; x < mx; ++x){
		int tx = x;
		int ty = 0;
		memcpy(visit, cpvisit, 4 * 32 * 12);
		while (1){
			if (ty >= my){
				if (tx == x) break;
				else return false;
			}
			if (map[ty][tx] == 1 && visit[ty][tx + 1] == 0){
				visit[ty][tx] = 1;
				++tx;
			}
			else if (map[ty][tx] == 2 && visit[ty][tx - 1] == 0){
				visit[ty][tx] = 1;
				--tx;
			}
			else{
				visit[ty][tx] = 1;
				++ty;
			}
		}
	}
	return true;
}

// 조합을 사용하기 때문에 for 문이 시작할 좌표 y, x 를 매개변수로 받는다
void dfs(int level, int y, int x){

	if (check() == true){
		if (minn > level) minn = level;
	}
	
	if (level == 3) return;

	int cpMap[32][12];
	memcpy(cpMap, map, 4 * 32 * 12);

	for (int i = y; i < my; ++i){
		for (int j = x; j < mx; ++j){
        // 현재 좌표와 현재 좌표의 오른쪽 모두 사다리가 없을 때 사다리 두기
			if (map[i][j] == 0 && j + 1 < mx && map[i][j + 1] == 0){
				map[i][j] = 1;
				map[i][j + 1] = 2;
				dfs(level + 1, i, j + 1);
				memcpy(map,cpMap, 4 * 32 * 12);
			}
		}
        // 매개변수로 받은 x축을 모두 탐색했을때 y가 증가하며 x를 0으로 초기화
		x = 0;
	}
}

int main(){
	//freopen_s(new FILE*, "tes.text", "r", stdin);
	cin >> mx >> h >> my;

	for (int i = 0; i < h; ++i){
		int y, x;
		cin >> y >> x;
		map[y - 1][x - 1] = 1;
		map[y - 1][x] = 2;
	}

	dfs(0, 0, 0);
	if (minn > 3) printf("-1");
	else printf("%d", minn);
}