[BOJ] #15684 _ 사다리 조작

[사다리 조작] https://www.acmicpc.net/problem/15684

15684번: 사다리 조작

사다리를 map이라는 이차원 배열을 이용하여 사다리의 상태를 저장해주었다.

가로선이 이어질 수 없기 때문에 배열로 아래와 같이 저장할 수 있다.

 

사다리의 결과를 확인 할 때는 map의 값이 0이면 아래로 내려가고,

숫자가 들어 있는 경우에는 해당 숫자의 인덱스로 넘어간 후 아래로 내려가도록 구현하였다.

그렇게 최종적으로 출발한 인덱스의 번호와 도착한 인덱스의 번호가 같은지 확인해주었다.

 

가로선을 추가할 때도 같은 형식으로 추가해주었고,

dfs를 이용하여 추가 가능한 경우의 수를 모두 고려하여 최소 값을 얻었다.

 

[ 소스 코드 ]

#include <cstdio>
#include <algorithm>

using namespace std;

int N, H, result = 4;
int map[31][11];

void solve(int cnt, int y, int x);
int checkRight();
int main() {
	int M, y, x;

	scanf("%d %d %d", &N, &M, &H);
	for (int i = 0; i < M; i++) {
		scanf("%d %d", &y, &x);
		map[y][x] = x + 1;
		map[y][x + 1] = x;
	}

	if (checkRight()) result = 0;
	else solve(1, 1, 1);

	if (result == 4) result = -1;
	printf("%d\n", result);

	return 0;
}

void solve(int cnt, int y, int x) {
	int next;
	if (cnt > 3) return;
	for (int i = y; i <= H; i++) {
		for (int j = x; j < N; j++) {
			next = j + 1;
			if (map[i][j] == 0 && map[i][next] == 0) {
				map[i][j] = next;
				map[i][next] = j;

				if (checkRight()) {
					result = min(result, cnt);
					map[i][j] = 0;
					map[i][next] = 0;
					return;
				}

				solve(cnt + 1, i, next);
				map[i][j] = 0;
				map[i][next] = 0;
			}
		}
		x = 1;
	}
	return;
}

int checkRight() {
	int x, y;
	for (int i = 1; i <= N; i++) {
		x = i;
		y = 1;
		while (y <= H) {
			if (map[y][x] > 0) x = map[y][x];
			y++;
		}
		if (i != x) return 0;
	}
	return 1;
}