JUST WRITE IT. HomeArchivesTagsCategories
백준 15684번 사다리 조작
|AlgorithmBOJ|

#15684. 사다리 조작

Problem

Solution

  • 처음에 감이 안잡혀서 어떻게 풀지 막막했었다.
  • 입력값을 보고 사다리 정보를 어떤 식으로 저장할건지가 첫 스타트이자 포인트다.
    이렇게 data가 보여야 조합도 어떤식으로 구성할지 생각나기 때문이다.
  • 작업은 2개로 나뉜다.
    1. 조합 구하기
    2. 사다리 타기
  • 조합 구하기

조합을 구하기 전에 입력값이 어떻게 들어오나 확인해보자.

a b가 입력되면 a행에 b열 사다리와 b+1열 사다리가 연결된다.
이를 array[a][b] = 1(사다리 있음)으로 표시하면 b+1로 갈 수 있다는 뜻이다.
반대로 b+1지점에서 array[a][b]값이 1인걸 확인하면 b로 갈 수 있다는 뜻이다.

이를 활용하여 조합을 구해보자.

모든 행의 1열부터 N-1열까지 탐색해야 한다.
단, 현재 위치뿐만 아니라 자신의 왼쪽, 오른쪽도 확인해야 한다. (연속으로 설치하지 못하기 때문)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
1행 1열 선택 시 다음 가능한 경우 (N에 표시하는 것은 의미 X - 입력값 생각)
 1행 - 1(x), 2(x), 3 ... N-1
 2행 - 1, 2, 3 ... N-1
 ...
 H행 - 1, 2, 3 ... N-1

for (int i = idx; i <= H; ++i) {
		for (int j = 1; j < N; ++j) { 
			if (visit[i][j]) continue; // 현재 확인
			if (j > 1 && visit[i][j - 1]) continue; // 왼쪽 확인
			if (visit[i][j + 1]) continue; // 오른쪽 확인
			visit[i][j] = true; // 선택 표시
			selectAll(i, cnt + 1); // 다음 선택
			visit[i][j] = false; 
		}
}

1 Try

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <iostream>
using namespace std;
int N, M, H, ans;
bool visit[31][11];
void Input() {
	ans = 4;
	cin >> N >> M >> H;
	for (int i = 0; i < M; ++i) {
		int a, b;  cin >> a >> b;
		visit[a][b] = true; // a행 b - b+1 사다리
	}
}
bool Check() {
	for (int j = 1; j <= N; ++j) {
		int current_num = j;
		for (int i = 1; i <= H; ++i) {
			if (visit[i][current_num]) { // 오른쪽 사다리로 이동
				current_num++;
			}
			else if (current_num > 1 && visit[i][current_num -1]) { // 왼쪽 사다리로 이동
				current_num--;
			}
		}
		if (current_num != j) return false;
	}
	return true;
}
void selectAll(int idx, int cnt) {
	if (cnt > ans) return;
	if (cnt == 4) {
		return;
	}
	if (Check()) {
		if (ans > cnt) ans = cnt;
		return;
	}
	for (int i = idx; i <= H; ++i) {
		for (int j = 1; j < N; ++j) { // 5번 사다리는 확인할 필요 없다. (입력값 생각)
			if (visit[i][j]) continue;
			if (j > 1 && visit[i][j - 1]) continue;
			if (visit[i][j + 1]) continue;
			visit[i][j] = true;
			selectAll(i, cnt + 1);
			visit[i][j] = false;
		}
	}
}
void Solve() {
	Input();
	selectAll(1, 0);
	if (ans == 4) ans = -1;
	cout << ans << "\n";
}
int main() {
	Solve();
	return 0;
}
Algorithm