[백준 15684] 사다리 조작

문제 링크 => 15684번: 사다리 조작 (acmicpc.net)

15684번: 사다리 조작

---

삼성 역량 테스트 문제로 BFS + Backtracking 문제이다.

 

문제 접근방법은 다음과 같다.

 

1. 위치 (i, j) 에 대하여 함수 f(i, j) 를 해당 위치에 대한 index값이라 할 때 f(i, j) = (i - 1)*N + j 라고 한다.

이때, (i, j) ~ (i, j+1) 의 길을 이어주는 방법은 path[f(i, j)][f(i, j+1)] = path[f(i, j+1)][f(i, j)] = 1 으로 설정할 수 있다.

 

2. 현재 위치 (i, j)를 기준으로 (i, j) ~ (i, j-1) 와 (i, j) ~ (i, j+1) 의 길이 동시에 이어지지 않은 경우 (i, j) ~ (i, j+1) 의 길을 이어줄 수 있다.

 

3. 위에서 아래로 탐색하는 과정에서 중간지점(1과 H 사이)에서 처음으로 사다리를 놓는 경우 다시 1로 이동하는 것이 아니라 중간지점부터 탐색을 이어가도록 해야한다. 

즉, 현재 높이에 대한 정보를 재귀적으로 함수를 호출할 때 보내야 하는 것이 핵심이다.

 

4.  3번을 넘어서 탐색하게 되는 경우를 Cut 하도록 해줘야 한다. (Backtracking)

 

5. 사다리를 놓을 수 있는 경우가 없는 경우(INF) -1을 반환하고 그 외에 사다리를 놓을 수 있는 개수의 최솟값을 반환하도록 한다.

 

풀이 Code

 

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#define INF 1000000000
#define endl '\n'
#define ll long long

using namespace std;

int N, M, H;
int path[302][302];

int f(int x, int y) {
	return (x - 1) * N + y;
}

void input() {

	cin >> N >> M >> H;
	for (int i = 0; i < M; i++) {
		int a, b;
		cin >> a >> b;
		path[f(a, b)][f(a, b + 1)] = path[f(a, b + 1)][f(a, b)] = 1;
	}
}

int isStraight(int x) {
	int step = 1, cur = x;
	while (step <= H) {
		if (path[f(step, cur)][f(step, cur + 1)]) cur += 1;
		else if (path[f(step, cur)][f(step, cur - 1)]) cur -= 1;
		step++;
	}

	if (cur == x) return 1;
	return 0;
}

int allStraight() {
	for (int i = 1; i <= N; i++) {
		if (!isStraight(i)) return 0;
	}
	
	return 1;
}

int solve(int curX, int cnt) {
	if (allStraight()) return cnt;
	if (cnt == 3) return INF;

	int ret = INF;
	for (int i = curX; i <= H; i++) {
		for (int j = 1; j <= N; j++) {
			if (!path[f(i, j)][f(i, j - 1)] && !path[f(i, j)][f(i, j + 1)]) {
				path[f(i, j)][f(i, j + 1)] = path[f(i, j + 1)][f(i, j)] = 1;
				ret = min(ret, solve(i, cnt + 1));
				path[f(i, j)][f(i, j + 1)] = path[f(i, j + 1)][f(i, j)] = 0;
			}
		}
	}

	return ret;
}

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

	input();
	int result = solve(1, 0);
	if (result == INF) cout << -1;
	else cout << result;

	return 0;
}