(c++)백준 15684번: 사다리 조작

www.acmicpc.net/problem/15684

15684번: 사다리 조작

[풀이]

dfs 조합 구하는 방법을 이용하여 풀어야하는 문제였다.

먼저 사다리는 Ladder[11][11][31]로 표현하였다. Ladder[b][b+1][a] = true는 b번 세로선과 b+1번 세로선이 a번째줄의 가로선에 의해 연결되었다는 뜻이다.

dfs로 추가할 가로선을 선정하고 0번 이상 추가했으면(3번 이하로) i번 세로선의 결과가 i번이 나오는지 확인하고 최솟값을 갱신한다.

 

※착각해서 조합을 구하지 않고 순열을 구했더니 시간초과가 났다. 순열과 조합 중 뭘 써야 하는지 정확히 인지하기!

 

#include <iostream>
using namespace std;

int N, M, H;
bool Ladder[11][11][31];
int Min = 987654321;

//조작 성공했는지
bool Check() {
	//각 세로선 확인
	for (int i = 1; i <= N; i++) {
		int col = i;
		for (int j = 1; j <= H; j++) {
			//왼쪽으로
			if (col != 1 && Ladder[col][col - 1][j] == true)
				col--;
			//오른쪽으로
			else if (col != N && Ladder[col][col + 1][j] == true)
				col++;
		}
		if (col != i)
			return false;
	}
	return true;
}

void getRow(int col, int row, int cnt) {
	if (cnt > 3 || cnt >= Min)
		return;
	if (cnt >= 0) {
		if (Check()) {
			Min = cnt;
			return;
		}
	}
	for (int i = col; i < N; i++) {
		for (int j = row; j <= H; j++) {
			if (Ladder[i][i + 1][j] == true)
				continue;
			//가로선 추가
			Ladder[i][i + 1][j] = true;
			Ladder[i + 1][i][j] = true;
			getRow(i, j, cnt + 1);
			Ladder[i][i + 1][j] = false;
			Ladder[i + 1][i][j] = false;
		}
		row = 1;
	}
}

void solution() {
	cin >> N >> M >> H;
	for (int i = 0; i < M; i++) {
		int a, b;
		cin >> a >> b;
		//b번 세로선과 b+1번 세로선 a번 점선 위치에서 연결
		Ladder[b][b + 1][a] = true;
		Ladder[b + 1][b][a] = true;
	}
	getRow(1,1,0);
	if (Min == 987654321)
		Min = -1;
	cout << Min << '\n';
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	solution();
	return 0;
}