[백준] 15684번 사다리조작 (C++, 삼성 기출)

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

시간초과가 많이 나서 고생한 문제이다.
사다리 게임의 판을 map 변수에 넣어주고, 사다리가 있을 때 왼쪽에는 1, 오른쪽에는 -1을 넣어줬다.
또한, 사다리를 설치할 때, 무조건 왼쪽에서만 설치하게 해서 중복을 막았다.

처음에 틀린 부분은 재귀로 다시 들어올 때 2중 for문을 이용해서 처음부터 탐색하려고 해서 시간초과가 났다.
이부분을 vector를 이용해 탐색을 줄여줘서 시간초과를 없앴다.

    // vector를 이용한 탐색
	// 왼쪽과 오른쪽 모두 0일 때,
	// 사다리를 설치해준다.
	for(int i = idx; i < v.size(); i++) {
		point cur = v[i];
		if(map[cur.y][cur.x] == 0 && map[cur.y][cur.x + 1] == 0){
			map[cur.y][cur.x] = 1; map[cur.y][cur.x + 1] = -1;
			solve(i+1, depth + 1);
			map[cur.y][cur.x] = 0; map[cur.y][cur.x + 1] = 0;
		}
	}

이부분이 메인 로직이다.
왼쪽과 오른쪽에 사다리가 없을 경우, 재귀를 통해 사다리를 설치해준다.

또한, depth가 3 이전에 답이 나올수도 있으니, 재귀로 들어가는 매 순간 사다리를 내려서 계산해줘야한다.

	// 사다리를 내려보는 함수
	int cnt = 0;
	for (int i = 1; i <= n; i++) {
		int y = 1;
		int x = i;
		// map이 1일 때, 사다리가 왼쪽으로 있으므로 x++
		// map이 -1일 때, 사다리가 오른쪽으로 있으므로 x--
		while (y <= h) {
			if (map[y][x] == 1) x++;
			else if (map[y][x] == -1) x--;
			// 한칸 내려준다.
			y++;
		}
		// 시작과 끝이 같으면 cnt++
		if (i == x)
			cnt++;
		else
			break;
	}

그 부분은 위의 방법으로 계산해줬다.
모든 세로줄에 대해서 map이 1일 때 오른쪽으로 가고, map이 -1일 때 왼쪽으로 가서 이동해주면 된다.

전체 코드

#include <iostream>
#include <vector>

using namespace std;

int n, m, h;
int map[31][11];
int answer = 987654321;
struct point {
public:
	int x;
	int y;
	point(int x, int y) {
		this->x = x;
		this->y = y;
	}
};
vector<point> v;

void solve(int idx, int depth) {
	// 3개 초과될 때 return
	if (depth == 4)
		return;
	
	// 사다리를 내려보는 함수
	int cnt = 0;
	for (int i = 1; i <= n; i++) {
		int y = 1;
		int x = i;
		// map이 1일 때, 사다리가 왼쪽으로 있으므로 x++
		// map이 -1일 때, 사다리가 오른쪽으로 있으므로 x--
		while (y <= h) {
			if (map[y][x] == 1) x++;
			else if (map[y][x] == -1) x--;
			// 한칸 내려준다.
			y++;
		}
		// 시작과 끝이 같으면 cnt++
		if (i == x)
			cnt++;
		else
			break;
	}

	// 사다리가 모두 자기자신으로 내려오면 
	// answer 갱신
	if (cnt == n) {
		answer = min(answer, depth);
	}

	// vector를 이용한 탐색
	// 왼쪽과 오른쪽 모두 0일 때,
	// 사다리를 설치해준다.
	for(int i = idx; i < v.size(); i++) {
		point cur = v[i];
		if(map[cur.y][cur.x] == 0 && map[cur.y][cur.x + 1] == 0){
			map[cur.y][cur.x] = 1; map[cur.y][cur.x + 1] = -1;
			solve(i+1, depth + 1);
			map[cur.y][cur.x] = 0; map[cur.y][cur.x + 1] = 0;
		}
	}
}

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;
		map[a][b] = 1;
		map[a][b + 1] = -1;
	}

	for (int i = 1; i <= h; i++)
		for (int j = 1; j < n; j++)
			if (map[i][j] == 0)
				v.push_back(point(j, i));

	solve(0,0);
	if (answer == 987654321)
		cout << "-1";
	else cout << answer;
}