백준 15684_사다리 조작(C++)

 

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

15684번: 사다리 조작

[문제 풀이]

시뮬레이션을 이용하여 문제를 풀었습니다.

이 문제는 시작 지점 사다리 번호와 도착 지점 사다리 번호를 같게 만드는 문제였습니다. 문제를 풀기 위해 2차원 배열에 사다리값을 받았고 이미 지정된 곳이 아니면서 양옆에 사다리가 놓이지 않은 곳을 찾아서 최대 3개까지 조합으로 놓아주는 문제였습니다.

사다리를 놓는 것은  selectLadder() 함수를 통해 확인해주었고, 시작 지점과 도착 지점이 같은가를 확인하는 것은 playGame() 함수를 통해서 해주었습니다.

[코드]

#include<iostream>

using namespace std;

#define MAX 987654321

int N, M, H;
int result = MAX;

int map[11][31] = { 0, };
bool check[11][31] = { false, };

void init();
void selectLadder(int, int);
bool playGame();

int main() {

	init();
	selectLadder(1, 0);

	if (result == MAX)
		printf("-1\n");
	else
		printf("%d\n", result);
}

void init() {

	scanf("%d %d %d", &N, &M, &H);

	for (int i = 0; i < M; i++) {
		int a, b;
		scanf("%d %d", &a, &b);

		check[a][b] = true;
	}

}

bool playGame() {

	for (int j = 1; j <= N; j++) {

		int point = j;

		for (int i = 1; i <= H; i++) {
			if (check[i][point])
				point++;
			else if (check[i][point - 1])
				point--;
		}

		if (point != j)
			return false;
	}
	return true;
}

void selectLadder(int idx, int cnt) {

	if (cnt > 3)
		return;

	if (playGame()) {
		result = (result < cnt) ? result : cnt;
		return;
	}

	for (int i = idx; i <= H; i++) {
		for (int j = 1; j <= N; j++) {

			if (check[i][j])
				continue;
			if (check[i][j - 1])
				continue;
			if (check[i][j + 1])
				continue;

			check[i][j] = true;
			selectLadder(i, cnt + 1);
			check[i][j] = false;

		}
	}

}