15684 사다리 조작

문제링크

😢코드 설명

사다리를 전부 한개씩 놓아보며 최소값을 찾는 완전탐색 문제이다.
물론 3개로 안될때 -1로 출력하라는 조건이없다면 시간초과가 발생할것이다.

하지만 그외에도 탐색시 조합과같이 구현하지 않는다면 이또한 시간초과가 발생한다.

사실이문제는 이중포문에서 y,x,now와 같이 변수설정하는데 시간이 더 걸렸다....ㅜㅜ

코드

	#include<iostream>
	#include<queue>
	#include<vector>
	using namespace std;
	int N, M, H;
	bool visited[31][11];
	int now;
	int temp;
	vector<pair<int, int>> abc;
	int answer = 99999;
	bool run() { //사다리 타기 시도 함수
	
		for (int now = 1; now <= N; now++) {
			temp = now;
			for (int y = 1; y <= H; y++) {

				if (visited[y][temp] == true) {
					temp = temp + 1;

				}
				else if (visited[y][temp - 1] == true && temp > 1 ) {
					temp = temp - 1;

				}

			}
			if (now != temp) return false;
		}
		return true;
	}
	void add(int idx, int cnt) { //가로선 추가 함수 

		if (cnt == 4) {
		
			return;
		}

		if (run() == true) {
			answer = min(answer, cnt);
			return;
		}


	for (int y = idx; y <= H; y++) {
		for (int x = 1; x <= N; x++) {
				if (visited[y][x] == true) continue;
				if (visited[y][x + 1] == true) continue;
				if (visited[y][x - 1] == true) continue;
				visited[y][x] = true;
				add(y, cnt + 1);
				visited[y][x] = false;
			}
		}

	}
	int main() {
		ios::sync_with_stdio(false);
		cin.tie(NULL);
		cout.tie(NULL);

		cin >> N >> M >> H;

		for (int i = 0; i < M; i++) {
			int a, b;
			cin >> a >> b;
			visited[a][b] = true;

		}
		if (M == 0) {
			cout << 0;
			return 0;
		}
		else {
			if (run() == true) {
				cout << 0;
				return 0;
			}
			else add(1,0);
		}

		if (answer == 99999) {
			cout << -1;
			return 0;

		}
		else {
			cout << answer;
		}
	
		return 0;
	}