(백준) 15684번 - 사다리 조작

문제

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

풀이

백트래킹으로 가로선을 설치하며 가장 최소로 설치하는 횟수를 구하면 된다.

이전에는 $O(N^2H)$을 가진 코드를 작성하여 시간복잡도가 발생했는데, 백트래킹 함수가 높이, 세로선 파라미터를 가지도록 하여 불필요한 탐색을 막았다.

코드

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

typedef pair<int, int> pii;

int n, m, h;
int line[31][11]; // line[i][j]: 높이 i에 가로선 (j, j + 1)이 존재함.
int ans = 4;

bool ladder() {
	for (int i = 1; i <= n; i++) {
		int cur = i;
		for (int j = 1; j <= h; j++) {
			// 출발 세로선: i, 높이: j

			// 높이 j에 (cur, cur + 1) 가로선이 존재하면
			if (line[j][cur]) {
				cur++;
			}
			// 높이 j에 (cur, cur - 1) 가로선이 존재하면
			else if (cur - 1 >= 1 && line[j][cur - 1]) {
				cur--;
			}
		}

		// 출발 i, 도착 i가 아니면
		if (cur != i)
			return false;
	}

	return true;
}

void dfs(int cnt,int curH,int curX) {
	if (cnt >= ans) {
		return;
	}

	if (ladder()) {
		ans = min(ans, cnt);
		return;
	}

	if (cnt == 3) {
		return;
	}

	for (int i = curH; i <= h; i++) {
		int start = 0;
		if (i == curH)
			start = curX;
		else
			start = 1;

		for (int j = start; j < n; j++) {
			if (line[i][j]) continue;
			if (line[i][j - 1]) continue;
			if (line[i][j + 1]) continue;

			line[i][j] = 1;

			dfs(cnt + 1, i, j + 2);

			line[i][j] = 0;
		}
	}
}

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

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

		line[a][b] = 1;
	}

	dfs(0, 1, 1);

	if (ans == 4) cout << -1;
	else cout << ans;
}

dfs(cnt + 1, i, j + 2); 에서 j + 2인 이유는 가로선은 인접할 수 없기 때문에 j + 1을 넘겨주어도 어차피 탐색이 진행되지 않기 때문이다.

시간복잡도

세로선의 개수는 $N$개, 가로선을 놓을 수 있는 높이의 수는 $H$이다. 따라서 가로선을 놓을 수 있는 위치의 수는 $(N-1) \cdot H$이다. 최대 3개를 선택할 수 있으므로 백트래킹 과정의 시간복잡도는 $O(_{(N-1) \cdot H} C _3)$이다. ladder 함수에서의 시간복잡도는 $O(NH)$이다. 전체 시간복잡도를 간략히 표현하면 $O((NH)^4)$이나, 실제로는 가지치기로 인해 깊은 탐색을 진행하지 않으므로 평균 속도는 더 빠르다.

공간복잡도

line 배열에서 $O(NH)$이고, 재귀함수는 최대 깊이가 3이므로 $O(1)$의 공간복잡도를 가진다. 따라서 총 공간복잡도는 $O(NH)$이다.