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

이 문제는 브루트포스와 백트래킹을 이용하는 구현 문제이다. 이 문제가 브루트포스 문제인것까지 생각했지만, 구현에서 막혔다. 어려운 구현 문제일수록 구현을 최대한 쉽게 하려는 노력이 필요한 것 같다. 

 

#include <iostream>
#include <algorithm>
using namespace std;

bool connected[100][100];
// n : 세로줄, m : 가로줄 개수, h : 가로 위치의 개수
int n, m, h;
int answer = INT32_MAX;

bool isCorrect()
{
	for (int i = 1; i <= n; i++)
	{
		int current = i;

		for (int j = 1; j <= h; j++)
		{
			if (connected[current][j])
			{
				current++;
			}
			else if (connected[current - 1][j])
			{
				current--;
			}
		}

		if (current != i)
		{
			return false;
		}
	}

	return true;
}

void func(int index, int cnt)
{
	if (cnt >= 4)
	{
		return;
	}

	if (isCorrect())
	{
		answer = min(answer, cnt);
		return;
	}

	for (int i = index; i <= h; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			if (connected[j][i])
			{
				continue;
			}
			if (connected[j - 1][i])
			{
				continue;
			}
			if (connected[j + 1][i])
			{
				continue;
			}

			connected[j][i] = true;
			func(i, cnt + 1);
			connected[j][i] = false;
		}
	}
}

int main()
{
	cin >> n >> m >> h;
	
	for (int i = 0; i < m; i++)
	{
		int a, b;

		cin >> a >> b;

		connected[b][a] = true;
	}

	func(1, 0);

	if (answer == INT32_MAX)
	{
		cout << -1 << '\n';
	}
	else
	{
		cout << answer << '\n';
	}

	return 0;
}

 

 

 

- 2024-03-25 2번째 풀이

 

이 문제를 1년만에 다시 풀었고, 이번에는 한번에 맞출 수 있었다. 시간 복잡도가 얼핏 안 맞아 보였는데, 가로선을 최대 3개까지만 깔 수 있기 때문에 가능하다. 270C1 + 270C2 + 270C3 은 1억 밑이기 때문이다.

 

사다리를 4차원 배열로 나타내어 문제를 풀었다. 단순히 가로선을 추가해주고, 가능한지 확인하는 과정만 코드로 나타내면 쉽게 풀 수 있다.

#include <iostream>
#include <string>
#include <vector>
using namespace std;

#define MAX 32

int N, M, H;
bool edge[MAX + 1][MAX + 1][MAX + 1][MAX + 1];
bool visited[MAX + 1][MAX + 1][MAX + 1][MAX + 1];

int execute(int y, int x) {
	if (y == H + 1) {
		return x;
	}

	int result = -1;

	// check left
	if (edge[y][x][y][x - 1] && !visited[y][x][y][x - 1]) {
		visited[y][x][y][x - 1] = true;
		visited[y][x - 1][y][x] = true;
		result = execute(y, x - 1);
		visited[y][x][y][x - 1] = false;
		visited[y][x - 1][y][x] = false;

	} else if (edge[y][x][y][x + 1] && !visited[y][x][y][x + 1]) {
		visited[y][x][y][x + 1] = true;
		visited[y][x + 1][y][x] = true;
		result = execute(y, x + 1);
		visited[y][x][y][x + 1] = false;
		visited[y][x + 1][y][x] = false;
	
	} else {
		result = execute(y + 1, x);
	}

	return result;
}

bool isPossible() {
	for (int i = 1; i <= N; i++) {
		int result = execute(0, i);
		
		if (result != i) {
			return false;
		}
	}
	
	return true;
}

bool addLine(int prevY, int prevX, int addCnt, int goalCnt) {
	if (addCnt == goalCnt) {
		if (isPossible()) {
			return true;
		}
		return false;
	}

	for (int y = prevY; y <= H; y++) {
		if (y == prevY) {
			for (int x = prevX; x <= N - 1; x++) {
				if (edge[y][x][y][x + 1]) {
					continue;
				}

				if (!edge[y][x][y][x - 1] && !edge[y][x + 1][y][x + 2]) {
					edge[y][x][y][x + 1] = true;
					edge[y][x + 1][y][x] = true;
					bool result = addLine(y, x, addCnt + 1, goalCnt);
					edge[y][x][y][x + 1] = false;
					edge[y][x + 1][y][x] = false;

					if (result) {
						return true;
					}
				}
			}
		
		} else {
			for (int x = 1; x <= N - 1; x++) {
				if (edge[y][x][y][x + 1]) {
					continue;
				}

				if (!edge[y][x][y][x - 1] && !edge[y][x + 1][y][x + 2]) {
					edge[y][x][y][x + 1] = true;
					edge[y][x + 1][y][x] = true;
					bool result = addLine(y, x, addCnt + 1, goalCnt);
					edge[y][x][y][x + 1] = false;
					edge[y][x + 1][y][x] = false;

					if (result) {
						return true;
					}
				}
			}
		}
	}

	return false;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> N >> M >> H;

	for (int i = 0; i < M; i++) {
		int a, b;

		cin >> a >> b;

		edge[a][b][a][b + 1] = true;
		edge[a][b + 1][a][b] = true;
	}

	if (isPossible()) {
		cout << 0 << '\n';

		return 0;
	}

	// add
	for (int cnt = 1; cnt <= 3; cnt++) {
		bool result = addLine(1, 1, 0, cnt);

		if (result) {
			cout << cnt << '\n';

			return 0;
		}
	}

	cout << -1 << '\n';

	return 0;
}