[BOJ] 15684번 사다리 조작

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

15684번: 사다리 조작

처음에는 단순한 dfs방법으로 풀릴 줄 알았지만 시간 초과로 인하여 오래 걸렸던 문제이다.

 

문제의 핵심 조건

1, 가로선이 연속적으로 일직선이 될 수는 없다.

 

2, 가로선이 겹치는 경우는 존재하지 않는다.

 

3, 정답이 3보다 크면 -1을 출력한다.

 

아이디어

1, dfs방식으로 다리를 놓을 수 있는 경우의 수를 탐색한다.

 

2, 문제의 조건에서 "정답이 3보다 크면 -1을 출력한다."는 조건으로 인하여 탐색 시간을 줄일 수 있다.

- 최소값을 찾는 문제이므로 정답은 0, 1, 2, 3, -1이 될 수 있는데 0부터 시작하여 해당 경우에 맞는 답을 찾으면 탐색을 종료한다.

 

-  위와 같은 방법을 사용하지 않을 시 dfs방식으로 답을 찾게 될 경우를 생각해 보자

예를 들어, dfs내에서 백 트래킹 방식으로 현재 찾은 기대값을 기준으로 탐색 여부를 판단하게 된다면 현재 찾은 최솟값이 2이면 2 이하인 정답을 계속적으로 찾게 된다.

계속 탐색을 진행하던 도중 1인 답이 나오면 이때까지 정답이 2인 경우를 찾게되는 계산이 불필요하게 들어가기 때문에  시간 초과 결과를 받게 된다.

 

3, <참고>

- 9프로대에서 "틀렸습니다" 결과를 받게 되었는데 하나의 세로선에도 여러 개의 가로선을 다른 가로선 위치에 넣어 줄 수 있는 것을 고려를 처음에 하지 못하였다.

 

#include <cstdio>
#include <vector>
#include <utility>
using namespace std;


int map[31][12][12];//첫번쨰 인자는 가로선의 개수, 두번째와 세번째는 이어진 것
int put_check[12];

int n = 0, m = 0, h = 0;


int res = -1;

bool check_correct() {

	int current_location;

	for (int i = 1; i <= n; i++) {
		current_location = i;
		//사다리를 타기 시작
		for (int j = 1; j <= h; j++) {
			if (current_location + 1 <= n) {
				if (map[j][current_location][current_location + 1] == 1) {
					current_location = current_location + 1;
					continue;
				}
			}
			if (current_location - 1 > 0) {
				if (map[j][current_location - 1][current_location] == 1) {
					current_location = current_location - 1;
					continue;
				}
			}
		}

		//최종적으로 같지 않다면 false를 반환
		if (current_location != i) return false;

	}
	return true;
}



void dfs(int input_cnt, int start_verticle_line, int cut_line) {


	if (cut_line == input_cnt) {

		if (check_correct()) {
			res = cut_line;
			return;

		}
		else {
			return;
		}
	}


	//선을 하나 추가하여 조사를 진행함
	for (int i = start_verticle_line; i <= n; i++) {
		for (int j = 1; j <= h; j++) {
			if (res != -1) return;

			if (i - 1 > 0) {
				if (map[j][i - 1][i] == 1) continue;
			}

			//이미 이어져 있는 곳인지 체크
			if (i + 1 <= n) {
				if (map[j][i][i + 1] == 1) continue;
			}

			//해당 경우가 아니라면 선을 놓고 조사를 진행
			map[j][i][i + 1] = 1;
			map[j][i + 1][i] = 1;
			dfs(input_cnt + 1, i,cut_line);
			map[j][i][i + 1] = 0;
			map[j][i + 1][i] = 0;

		}
	}


}

int main()
{
	int temp1, temp2;
	scanf("%d %d %d", &n, &m, &h);
	for (int i = 0; i < m; i++) {
		scanf("%d %d", &temp1, &temp2);
		map[temp1][temp2][temp2 + 1] = 1;
		map[temp1][temp2 + 1][temp2] = 1;
	}

	for (int i = 0; i <= 3; i++) {
		dfs(0,1,i);
		if (res != -1) break;
	}

	printf("%d\n", res);

	return 0;
}