백준 15694 사다리 조작

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

15684번: 사다리 조작

 

- 문제를 꼼꼼히 잘 읽어봐야 한다. 300C3의 경우의 수가 나온다. 

 

- 사다리는 최대 3개를 둘 수 있다. 또한, 사다리를 가로로 연달아서 둘 수 없다.

 

- visited[i][j]는, i번 세로선에서 i+1 세로선으로 이동할 때 사용된 가로선이 j라는 뜻이다. 즉, i에서 i+1로 이어질 때, 가로선 j가 사용 된 것이다. 

 

- 매번 가로선을 놓을 때 마다, test를 진행한다. 시간 초과를 막기위해 주어진 세로선 중 1개라도 자신의 번호에 도달하지 못하는 경우 false를 return하도록 한다.

 

- 난 시간초과가 떴다. 나와 동일한 logic으로도 통과한 사람들이 있는 걸 보면 대체 왜 시간초과가 나는지 모르겠다..ㅜㅜ

#include <iostream>
#include <algorithm>
using namespace std;
int answer = 4;
int n, m, h;
bool visited[11][30];
int map[11][30];

bool test() { // 주어진 조건을 만족하는 지를 체크하는 함수
	for (int i = 1; i <= n; i++) {
		int current_line = i;
		int t = 1;
		while (t <= h) {
			if (visited[current_line][t]) {
				current_line++;
			}
			else if (visited[current_line - 1][t]) current_line--;
			t++;
			
		}
		if (current_line != i) return false;
	}
	return true;
}

void DFS(int cnt, int index) { //사다리를 놓는 경우의 수
	if (cnt >= 4) return; // cnt가 4를 넘어가면 유망하지 않으므로 return
	if (test()) {
		answer = min(answer, cnt);
		return;
	}
	for (int i = index; i <= h; i++) {
		for (int j = 1; j < n; j++) {
			if (visited[j][i] || visited[j-1][i] || visited[j+1][i]) continue;
			visited[j][i] = true;
			DFS(cnt + 1, index+1);
			visited[j][i] = false;
		}
	}
}
int main() {
	cin >> n >> m >> h;
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		visited[b][a] = true;
	}
	DFS(0,1);
	if (answer == 4) answer = -1;
	cout << answer;
	return 0;
	
}