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

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

15684번: 사다리 조작

🔔 문제 : 

(2<= N <= 10) 인 N개의 가로 좌표(세로선 갯수),

(1<= H <= 30) 인 H개의 세로 좌표(가로선 갯수),

(0 <= M <= (N-1)*H )인 M개의 놓여진 사다리 갯수

가 있습니다.

 

예를 들면 N = 5, H = 6, M = 1입니다.

그리고 그 아래에는 놓여진 사다리의 위치 a , b  주어집니다.

a = 3,  b= 1  (즉, (1,3), (1,4)위치에 사다리가 이어집니다.)

 

문제는 1번 사다리를 탄사람은 1번, 2번은 2번, n번은 n번이 최종적으로 결정되게 사다리를 놓는 문제입니다.

 

여기서!,, 사다리를 3개보다 초과되게 놓거나, 사다리를 아무리 놓아도 조작이 안될 때 -1로 처리합니다.

 

사다리를 조작하려는데 놓아야하는 수의 최솟값을 출력하는 문제입니다.

---

🔔 Kick Point :

DFS를 이용하여 사다리를 놓아야하는 좌표를 조합을 이용해 경우의 수를 구해야합니다.

 

그리고 저는 왼쪽 상단의 좌표를 (1,1) 로 두고, 사다리를 놓는 경우는 사다리의 왼쪽점만 체크하였습니다.

이 좌표를 bool arr[11][31] 2차원 배열로 두어, 사다리가 놓여있으면 true, 아니면 false로 두었습니다.

 

또 중요한 점은, DFS 돌릴 때, 1차원으로 바꾼 걸 2차원으로 바꿨습니다.

for (int i = k; i < (n - 1) * h; i++) {
   int x = i % (n - 1); // 0 ~ n-1
   int y = i / (n-1);
   x++; y++;
}

이 for문을 주의깊게 살펴보아야합니다. 이 부분은 x, y좌표값을

(1,1) -> (2, 1) -> (3, 1) -> (4,1) -> (1, 2) -> ...

요런식으로 탐색하게 만들어줍니다. (x좌표 젤 오른쪽은 사다리를 놓을 공간이 없으니깐 안해도됩니다.)

 

그리고, DFS() 매개변수에 놓아야하는 사다리 갯수 t 라는 값을 주어

0개 놓아야하는지, 1개 2개 3개 놓아야하는지를 따로따로 구할 수 있게 만들어줍니다.

 

사다리를 놓은 갯수가 t가 되었을 때 Play()함수를 통해 실제로 사다리를 타봅니다.

만약 답이 맞다면 그 t값을 출력하고, exit(0)함수로 main문을 빠져나오게 됩니다.

---

🔔 Code :

// BFS 완전탐색

#include <iostream>
using namespace std;


int n, m, h; // n 세로줄, m 현개 있는 가로줄, h: 가로줄  
bool arr[11][31] = {false,}; // (가로 n,  세로, h)

bool Play() {

	for (int row = 1; row <= n; row++)
	{
		int tmp = row;
		for (int col = 1; col <= h; col++) {

			if (arr[tmp][col]) {
				tmp++;  
			}
			else if (arr[tmp-1][col]) {
				tmp--;
			}
		}

		//cout << row << " : " << tmp << endl;
		if (tmp != row) return false;
		
	}
	return true;
}

void DFS(int cnt, int t, int k = 0) {

	if (cnt == t) {
		if (Play()) {
		cout << t << endl;
		exit(0);
		}
		
		return;
		
	}

	for (int i = k; i < (n - 1) * h; i++) {

		int x = i % (n - 1);  // 0 ~ n-1
		int y = i / (n-1);
		x++; y++;

		if (!arr[x-1][y] && !arr[x][y] && !arr[x + 1][y]) {
			arr[x][y] = true;
			DFS(cnt + 1, t, i+1);
			arr[x][y] = false;
		}
	}
}

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


	DFS(0, 0); DFS(0, 1); DFS(0, 2); DFS(0, 3);
	cout << -1;
}

 

++ 추가사항으로

void check() {
	for (int col = 1; col <= h; col++) {
		for (int row = 1; row <= n; row++) {
			cout << arr[row][col] << " ";
		}
		cout << "\n";
	}
	cout << '\n';
}

저는 요론식으로  check()함수를 써가며 좌표가 제대로 되어있는지 확인했습니다.

---