[BOJ] 15684 사다리타기 (c++)

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

15684번: 사다리 조작

 

 

#include <iostream>
using namespace std;

// DFS
int n, m, h;
int map[32][12];
int res = 987654321;

bool draw() {
	
	for(int x=1; x<=n; x++) {
		int cur_x = x;
		for(int y=1; y<=h; y++) {
			if(map[y][cur_x] == 1) cur_x++;
			
			else if(map[y][cur_x-1] == 1) cur_x--;
		}
		if(cur_x != x)
			return false;
	}

	return true;
}


void DFS(int y, int x, int dep) {
	if(res <= dep) return; // 가지치기

	if(draw()) {
		res = dep;
		return;
	}
    if(dep == 3) return;

	for(int cy=y; cy<=h; cy++) {
		for(int cx =x; cx<=n; cx++) {
        	// 가로선은 인접하면 안됨
			if(map[cy][cx] != 0 || map[cy][cx-1] != 0 || map[cy][cx+1] != 0) continue;
			map[cy][cx] = 1;
			DFS(cy, cx, dep+1);
			map[cy][cx] = 0;
			
		}
		x = 1;
	}
}



int main() {
	scanf("%d %d %d", &n, &m, &h);

	for(int i=0; i<m; i++) {
		int a, b;
		scanf("%d %d",&a, &b);
		map[a][b] = 1;
	}
	
	DFS(1, 1, 0);

    if(res > 3)
        printf("-1\n");
    else
	   printf("%d\n", res);

	return 0;

}

DFS 로 깊이가 3 이하인 경우들을 확인한다.