사다리조작 / 브루트포스

www.acmicpc.net/problem/15684

15684번: 사다리 조작

#include <iostream>
#include <algorithm>

using namespace std;

const int MAX = 30;
int n, m,h;
bool flag;
int ladderCnt;
bool ladder[MAX][11];


void DFS(int y, int cnt) {

	
	if (flag) return;

	if (ladderCnt == cnt) { //cnt
		
		bool possible = true;
		for (int i = 1; i <= n; i++) { //1부터 n열까지
			
			int row = i; 
			for (int j = 0; j < h; j++) {  //가로선을 놓을 수 있는 개수: h
				
				if (ladder[j][row]) // 오른쪽
					row++; 
				else if (row > 1 && ladder[j][row - 1])  //왼쪽
					row--; 
			}
			//열의 방향만 움직여 본다.

			if (i != row) { //최종적으로 처음의 열과 최종 열이 같지 않은 경우 
				
				possible = false; //false를 넣어줌
				break;
			
			}
					
		}
		if (possible) flag = true; // true를 넣어줌
		return;

	
	}

	for (int i = y; i < h; i++) {   
		for (int j = 1; j < n; j++) {
			
			// 두 가로선이 연속하거나 서로 접하면 안된다. 
			if (!ladder[i][j - 1] && !ladder[i][j] && !ladder[i][j + 1]) {
				

				ladder[i][j] = true; 
				DFS(i, cnt + 1); //재귀할때 x축만 전달하기 
				ladder[i][j] = false;
			
			}
		
		}
	}
	return;
}


int main() {
	
	cin >> n >> m >>h;

	for (int i = 0; i < m; i++) {
		
		int y, x;
		cin >> y >> x;
		ladder[y - 1][x] = true;
	
	}

	for (int i = 0; i <= 3; i++) {  //정답이 3보다 크면 -1을 출력하도록 한다. 
		ladderCnt = i; //허용하는 cnt 가 i
		
		DFS(0, 0); 
		
		if (flag) { //해당 cnt가 가능할 때,
		
			cout << ladderCnt << "\n"; 
			return 0;
		}
	}
	cout << -1 << "\n";
	return 0;

}

- 사다리의 열의 움직임만 파악하는 것이 관건