[#15684] 사다리 조작

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

vector<vector<int>> board;
int n, m, h;
int answer = 1000;

//범위 안에 있는지
bool inRange(int row, int col) {
	if (1 <= row && row < h + 1 && 1 <= col && col < 2 * n)
		return true;

	return false;
}

bool isAnswer() {
	int check = 0;
	for (int j = 1; j < 2 * n; j = j + 2) {
		//사다리 한 줄씩 확인
		int row = 1;  //처음 row부터
		int col = j;
		while (row <= h) {
			//왼쪽 가로선 확인
			if (inRange(row, col -1) && board[row][col - 1] == 1) {
				col = col - 2;  //있으면 이동
			}

			//오른쪽 가로선 확인
			else if (inRange(row, col + 1) && board[row][col + 1] == 1) {
				col = col + 2;  //있으면 이동
			}
			row++;  //밑으로도 한 칸
		}
		if (j == col) {
			check++;  //처음 시작한 곳과 끝난 곳이 같으면
		}
	}

	if (check == n)  //모두 처음 시작한 곳과 끝난 곳이 같으면
		return true;  //정답
	else
		return false;
}

//row, col에 사다리 가로 줄 놓을 수 있는가
bool isPossiblePut(int row, int col) {
	//내가 놓으려는 곳이 가로줄 첫 열이라면 연속 확인 필요 없음. 그냥 놓으려는 곳에 가로줄 없는지만 체크
	if (!inRange(row, col - 2) && board[row][col] == 0)
		return true;

	//이전 연속인가 확인
	if (inRange(row, col - 2) && board[row][col - 2] == 0 && board[row][col] == 0)
		return true;

	return false;
}

//cnt번째 할거야. row, col에 놓을거야
void recursive(int cnt, int row, int col) {
	if (isAnswer()) {
		//놓은건 cnt-1개이므로
		answer = min(answer, cnt - 1);
		return;  //최소값이니까 더 볼 필요 없음
	}

	if (cnt == 4) {
		return;
	}
	
	bool isFirst = true;
	for (int i = row; i < h + 1; i++) {
		for (int j = 2; j < 2 * n; j = j+2) {
			if (isFirst) {
				isFirst = false;
				j = col - 2;
				continue;
			}

			//i,j에 놓을 수 있다면
			if (isPossiblePut(i,j)) {
				board[i][j] = 1;  //놓기
				recursive(cnt + 1, i, j + 2);  //재귀
				board[i][j] = 0;  //원래대로
			}
		}
	}
}

int main() {
	scanf("%d %d %d", &n, &m, &h);
	board = vector<vector<int>>(h + 1, vector<int>(2 * n, 0));
	//board의 홀수 열은 사다리 세로 줄 있는 곳 (모두 1)
	//board의 짝수 열은 사다리 가로 줄 놓을 수 있는 곳

	//가로줄
	for (int i = 1; i <= m; i++) {
		int a, b;
		scanf("%d %d", &a, &b);
		board[a][2 * b] = 1;
	}

	//세로줄
	for (int i = 1; i < h + 1; i++) {
		for (int j = 1; j < 2 * n; j = j + 2) {
			board[i][j] = 1;
		}
	}
	
	//////////////

	recursive(1, 1, 2);

	if (answer == 1000)  //답 없다면
		printf("-1\n");
	else
		printf("%d\n", answer);

	return 0;
}

완전탐색

 

사다리를 어떻게 표현할지 고민한 문제... 홀수열은 세로줄, 짝수열은 가로줄을 놓기로 하고 진행함

 

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

15684번: 사다리 조작