[백준 15684번 - 사다리 타기] C++ 풀이

백준 15684번.

사용한 알고리즘

- 백트래킹

- 구현

 

어떻게 풀어야 할지는 빠르게 생각이 났었다.

h 행 * n 열 짜리 배열을 만든다. 가로행은 몇번째 가로선에 사다리를 놓을지를 나타내고, 세로열은 몇번째 세로선에 사다리를 놓을지 나타낸다. 세로선을 기준으로 오른쪽방향만 저장하려고 한다. 예를들면, 1번 세로선과 2번 세로선 사이에 위에서 2번째 지점에 사다리를 놓는다면 arr[2][1] = 1이 된다.

가지를 치는 기준은 depth 가 3이 될 경우, 또는 depth 가 3이 되기 전, 이미 i번째 세로선이 i번째로 통과되는 경우이다. 

 

애를 먹었던 부분은 

1) 9% 에서 시간초과 -> 이는 매번 dfs 를 호출할 때마다 0번째 지점 0번째 사다리부터 검사해서 그런것같길래, dfs 인자로 인덱스를 넘겨 이미 검사한 지점은 다시 검사하지 않도록 해주었다.

2) 항상 최솟값만을 저장 -> 답을 도출할 때, 현재 답과 비교해서 최솟값을 넣어주어야 하는데, 무조건 대입하였다.. 그래서 계속 23%에서 틀렸다고 나오더라.. 해당 문제에서는 답이 3이 넘어가면 -1을 출력하라고 했으니, 답 초기값을 4로 해주고, 답을 재저장할때는 무조건 기존 답과 비교해서 더 작은 값을 대입해주도록 바꾸었다. 답 == 4이면 -1을 출력하도록 하였다.

 

완성된 코드.

#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

int n, m, h;
int ans = 4;
vector<vector<int>> v;

bool isItoI() {
	for(int k = 0; k < n; ++k) {
		int curr = k; // 현재 위치한 세로선.
		for(int i = 0; i < h; ++i) {
			// 왼쪽, 오른쪽을 검사하여 사다리가 있는지 검사한다.
			// curr == 0 일때는 오른쪽만, cur == n - 1 일때는 왼쪽만 검사한다.
			if (curr == 0) {
				if (v[i][curr] == 1) {
					curr += 1;
				}
			} else if (curr == n - 1) {
				if (v[i][curr - 1] == 1) {
					curr -= 1;
				}
			} else {
				if (v[i][curr] == 1) {
					curr += 1;
				} else if (v[i][curr - 1] == 1) {
					curr -= 1;
				}
			}
		}
		if (curr != k)
			return false;
	}
	return true;
}

void dfs(int depth, int w) { // w -> 사다리 놓을 곳 검사한 곳은 다시 검사하지 않는다.
	// 세로선 i가 i에 가는지 검사.
	if (isItoI()) {
		ans = min(ans, depth); // 작은지 비교하는 검사 필수!!
		return;
	}
	if (depth == 3) {
		// 세로선 i가 i에 가는지 검사.
		if (isItoI())
			ans = min(ans, depth);
		return;
	} else {
		for(int i = w; i < h; ++i) {
			for(int j = 0; j < n - 1; ++j) {
				// v[i][j] == 0 이고,
				// v[i][j - 1] == 0 v[i][j + 1] == 0 일때
				// 거기다가 다리 놓고 dfs.
				if (j == 0 && v[i][j] == 0 && v[i][j + 1] == 0) {
					v[i][j] = 1;
					dfs(depth + 1, i);
					v[i][j] = 0;
				} else if (j > 0 && v[i][j] == 0 && v[i][j - 1] == 0 && v[i][j + 1] == 0) {
					v[i][j] = 1;
					dfs(depth + 1, i);
					v[i][j] = 0;
				}
			}
		}
	}
}

int main() {
	scanf("%d %d %d", &n, &m, &h);

	v.assign(h + 1, vector<int>(n + 1, 0));
	for(int i = 0; i < m; ++i) {
		int a, b;
		scanf("%d %d", &a, &b);
		v[a - 1][b - 1] = 1;
	}
	dfs(0, 0);
	printf("%d\n", (ans == 4) ? -1 : ans);
}