BOJ 15684번 : 사다리 조작 - C++

Q. 문제

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

15684번: 사다리 조작

A. 풀이

 

#include <iostream>
#include <vector>
using namespace std;
int N, M, H, a, b, map[32][12];
bool result = false;
vector<pair<int, int>> v;

bool chk() {
	for (int j = 1; j <= N; j++) {
		int x = 0, y = j;
		while (x <= H) {
			x++;
			if (map[x][y] == 1) {
				y++;
			}
			else if (map[x][y - 1] == 1) {
				y--;
			}
		}
		if (j != y) return false;
	}
	return true;
}
void dfs(int x, int y, int cnt, int total) {
	if (result) return;
	if (cnt == total) {
		result = chk();
		return;
	}
	for (int j = 1; j < N; j++) {
		for (int i = x; i <= H; i++) {
			if (i == x && j == y) continue;
			if (map[i][j - 1] || map[i][j] || map[i][j + 1]) continue;
			map[i][j] = 1;
			dfs(i, j, cnt + 1, total);
			map[i][j] = 0;
			while (1) {
				if (i >= H) break;
				if (map[i + 1][j - 1] || map[i + 1][j + 1]) break;
				i++;
			}
		}
	}
}
int main() {
	cin >> N >> M >> H;
	for (int i = 0; i < M; i++) {
		cin >> a >> b;
		map[a][b] = 1;
	}

	if (M == 0) {
		cout << "0\n";
	}
	else {
		int num = 0;
		for (num = 0; num <= 3; num++) {
			dfs(1, 1, 0, num);
			if (result) break;
		}
		if (result) cout << num << "\n";
		else cout << "-1\n";
	}
	return 0;
}

 

620 MS로 짰다가 아이디어를 추천받아서 0 MS로 줄였습니다.

역시 세상에 똑똑한 분들이 너무 많아.... ㅎㅎㅎㅎㅎ

​

1. 사다리의 좌표에서 양 옆에 사다리가 놓이지 않았다면 사다리를 설치해주는 조합 (DFS) 구성

2. 설치된 사다리의 각 y좌표의 맨 위에서 아래로 내려가면서 사다리가 있으면 오른쪽으로,

오른쪽으로 가는 사다리가 없지만 왼쪽에 사다리가 있으면 왼쪽으로 움직임

3. H까지 내려갔는데 출발지와 위치가 다르면 return false

4. 백트래킹으로 맵을 되돌려서 완전 탐색

5. 최초 성공 시까지 반복하다가, 성공하면 탐색 중단

 

while (1) {
	if (i >= H) break;
	if (map[i + 1][j - 1] || map[i + 1][j + 1]) break;
		i++;
}

+ 시간 줄이는 아이디어

두 사다리사이에 사다리 하나를 놓고 밑으로 내려갈 때,

양쪽에 사다리가 존재하지 않으면 그 사이에 사다리를 놓아도 다시 제자리로 돌아갑니다.

그러면 사다리를 놓는 의미가 없으므로 사다리를 놓지 않게 건너뛰어주는 코드입니다.

​

코드는 단순한데 아이디어를 생각하기 어려운 부분...

그냥 완탐으로 풀면 안 되나 했지만 속도 줄어드는거 보니까 그래도 뿌듯하네여....