[백준] 사다리 조작

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

15684번: 사다리 조작

 

시간 초과 발생.

dfs를 돌 때마다 r이 1부터 돌아서 문제였다. idx를 저장해두고, 그 idx부터 for문 돌리니까 통과.

bool findPos(int idx, int cnt, int curr) {
	if (cnt == curr) {
		if (check()) {
			//print();
			return true;
		}
		return false;
	}
	for (int r = idx; r <= H; r++) {
		for (int c = 1; c < N; c++) {

...
				if (flag) {
					bool result = findPos(r, cnt, curr + 1);
					if (result) {
						return true;
					}
					board[r][c] = 0;
				}
			}
		}
	}
	return false;
}

 

전체 코드

#define _CRT_SECURE_NO_DEPRECATE

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

int answer;
int N, M, H;
vector< vector<int>> lines; // {가로선, 세로선}
int board[32][12];

void init() {

}

void input() {
	cin >> N >> M >> H;

	for (int i = 0; i < M; i++) {
		int a, b;
		cin >> a >> b;
		lines.push_back({ a,b });
		board[a][b] = 1;
	}
}

bool inRange(int r, int c) {
	return r >= 1 && r <= H && c >= 1 && c <= N;
}

void print() {
	for (int r = 1; r <= H; r++) {
		for (int c = 1; c <= N; c++) {
			cout << board[r][c] << " ";
		}
		cout << endl;
	}
	cout << endl;
}

bool check(){
	for (int c = 1; c <= N; c++) {
		int idx = c;
		for (int r = 1; r <= H; r++) {
			if (board[r][idx] == 1) {
				idx = idx + 1;
			}
			else if (idx-1>=1 && board[r][idx-1] == 1) {
				idx = idx - 1;
			}
			//cout << idx << endl;
		}
		if (idx != c) {
			return false;
		}
	}
	return true;
}

bool findPos(int idx, int cnt, int curr) {
	if (cnt == curr) {
		if (check()) {
			//print();
			return true;
		}
		return false;
	}
	for (int r = idx; r <= H; r++) {
		for (int c = 1; c < N; c++) {
			if (board[r][c] == 0) {
				bool flag = false; // 가로선을 놓았는지
				if (c - 1 < 1) {
					if (board[r][c + 1] == 0) {
						board[r][c] = 1;
						flag = true;
					}
				}
				else if (c + 1 == N + 1) {
					if (board[r][c - 1] == 0) {
						board[r][c] = 1;
						flag = true;
					}
				}
				else {
					if (board[r][c - 1] == 0 && board[r][c + 1] == 0) {
						board[r][c] = 1;
						flag = true;
					}
				}

				if (flag) {
					bool result = findPos(r, cnt, curr + 1);
					if (result) {
						return true;
					}
					board[r][c] = 0;
				}
			}
		}
	}
	return false;
}

void solve() {
	if (check()) { //바로 통과하는 경우
		answer = 0;
		return;
	}
	for (int i = 1; i <= 3; i++) {
		if (findPos(1, i, 0)) {
			answer = i;
			return;
		}
	}

	answer = -1;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	//freopen("input.txt", "r", stdin);

	init();
	input();
	solve();

	cout << answer << endl;
	return 0;
}