[백준] 15684-사다리 조작(C++)

문제링크:https://www.acmicpc.net/problem/15684

15684번: 사다리 조작

 

전형적인 브루트포스 문제입니다.

 만약, 정답이 3보다 큰 값이면 -1을 출력한다. 

이라는 조건이 있기 때문에 모든 경우의 수를 대입해서 결과를 유추할 수 있기 때문입니다.

 

저는 크게 두가지 기능으로 분류했습니다.

 

1. 경로를 선택하는 함수 SELECTED 

2. 해당 사다리가 올바르게 i번 세로선의 결과가 i번이 나오는지 확인하는 함수 JUDMENT

 

2번 함수 같은 경우에는 쉽게 구현이 가능합니다.

bool judment() {


	for (int i = 1; i <= n; i++) { //세로 

		int ii = i; //열

		for (int j = 1; j <= h; j++) {
			if (arr[j][ii] == 1)
				ii++;
			else if (arr[j][ii - 1] == 1) {
				ii--;
			}
		}

		if (ii != i)
			return false;
	}

	return true;
}

1번 함수같은 경우에는 조금 해맸는데, DFS를 사용해서 구현하였습니다.

 

void selected(int y, int cnt) {
	if (flag == true)
		return;

	if (cnt == leadercnt) {
		flag = judment();

		return;
	}

	for (int i = y; i <= h; i++) {
		for (int j = 1; j < n; j++) {
			if (arr[i][j] == 0 && arr[i][j - 1] == 0 && arr[i][j + 1] == 0)
			{

				arr[i][j] = 1;
				selected(i, cnt + 1);
				arr[i][j] = 0;
			}

		}
	}

	return;
}

 

FLAG값이 참이거나 원하는 CNT값과 같거나 큰 경우에는 더 진행할 필요가 없기때문에 RETURN;을 통해서 함수를 종료하였습니다. 그리고 매개변수 Y을 사용하여서 기존에 검사했던 좌표들을 중복으로 검사하지 않게끔 구현하였습니다. 

 

 

 

정답코드입니다.

/*
1. 선택하는 함수  selected
경로를 선택, visited에 쓰고 다시 지우고 판단함수 호출
2. 판단하는 함수  judment
반복문을 돌며 올바르게 동작하면 cnt값을 전달하게 끔
*/
#include <iostream>
using namespace std;

int n = 0, m = 0, h = 0;
bool arr[32][12] = { 0 };
int cnt = 0;
int leadercnt;


bool flag;

bool judment() {


	for (int i = 1; i <= n; i++) { //세로 

		int ii = i; //열

		for (int j = 1; j <= h; j++) {
			if (arr[j][ii] == 1)
				ii++;
			else if (arr[j][ii - 1] == 1) {
				ii--;
			}
		}

		if (ii != i)
			return false;
	}

	return true;
}


void selected(int y, int cnt) {
	if (flag == true)
		return;

	if (cnt == leadercnt) {
		flag = judment();

		return;
	}

	for (int i = y; i <= h; i++) {
		for (int j = 1; j < n; j++) {
			if (arr[i][j] == 0 && arr[i][j - 1] == 0 && arr[i][j + 1] == 0)
			{

				arr[i][j] = 1;
				selected(i, cnt + 1);
				arr[i][j] = 0;
			}

		}
	}

	return;
}




int main() {
	

	int a = 0, b = 0;

	cin >> n >> m >> h;
	for (int i = 0; i < m; i++) {
		cin >> a >> b;
		arr[a][b] = 1;
	}

	for (int i = 0; i <= 3; i++) {
		flag = false;
		leadercnt = i;
		selected(1, 0);

		if (flag == true) {
			cout << i << "\n";
			return 0;
		}
	}

	cout << -1 << "\n";
	return 0;

}