백준 15684 사다리 조작

작성일 | In |

Problem : 사다리조작

유형 : Backtracking

문제, 예제 입출력 설명

그림이 많아 링크로 대체합니다

해결 전략

가지치기에 굉장히 신경을 써야한다.
답이 될수 없는경우, 바로 가지치기를 해야한다.
사다리를 놓을때, 사다리를 놓을 수 있는곳인지를 확인한다.

주의할 점

  • 사다리를 추가할때마다 시뮬레이션을 돌리면 시간초과가 발생한다.
  • 사다리를 추가할떄마다 끝점을 갱신하는 방법도 시간초과가 발생했다.
    • 사실 저지에 제출하기전에 확인하니, 시간초과가 충분히 발생할만큼 오래걸렸다.
    • 이 방법으로 통과하신분들도 있다는데, 나는 통과 못했을꺼 같다.
  • 다음 사다리를 놓으러 갈때, 사다리 경우의 수 for문을 주의해야 한다.
    • 해당 높이에서 모든 사다리를 접근했으면
    • 다시 1번위치의 사다리부터 점검해야한다. 초기화 위치 조심
  • 최대 놓을 수 있는 사다리는 3개이다.

풀이

사다리를 놓아본다

  • 사다리를 놓을 수 있는지 확인한다
  • 놓을 수 없다면 그냥 지나간다
  • 다음 사다리를 놓을때, 변수 초기화에 신경쓰자. ladder_num = 1;

사다리를 시뮬레이션해본다

  • 초기 현재위치는 자명하게 시작위치이다.
  • 만약 사다리가 놓여 있다면 우측으로 갈 수 있다는 이야기이다.
    • 현재 위치를 한칸 우측으로 바꾼다 cur_spot++
  • 만약 바로 좌측에 놓여있다면, 좌측으로 갈 수 있다는 이야기이다.
    • 현재 위치를 한칸 좌측으로 바꾼다 cur_spot--

가지치기를 한다

  • 현재 최적의 값과 비교한다.
  • 4이상인지 확인한다.
  • 만약 3일 경우, 답이 될 수 있다.
    • 하지만, 또 사다리를 놓는 경우는 답이 절대 될수 없다.
    • 이 부분에서 속도가 2배 이상 차이난다.

코드

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <bits/stdc++.h>
using namespace std;

bool ladder[32][12];

int n, m, h;
int answer = INT_MAX;

bool check() {
    for (int ladder_num = 1; ladder_num <= n; ++ladder_num) {
        int cur_spot = ladder_num;
        for (int height = 1; height <= h; ++height) {
            if (ladder[height][cur_spot])  cur_spot++;
            else if (ladder[height][cur_spot - 1]) cur_spot--;
        }
        if (cur_spot != ladder_num) return false;
    }
    return true;
}

bool add_ladder(int height, int ladder_num) {
    for (int i = -1; i <= 1; ++i) {
        if (ladder[height][ladder_num + i]) return false;
    }
    return true;
}


void dfs(int height, int ladder_num, int cur) {
    if (cur >= answer) return;
    if (check()) {
        answer = cur;
        return;
    }
    if (cur == 3) return;
    //3일때 가지치기.

	for (int a = height; a <= h; ++a) {
		for (int b = ladder_num; b <= n-1; ++b) {

			if (!add_ladder(a, b))continue;
			ladder[a][b] = true;
			dfs(a, b + 1, cur + 1);
			ladder[a][b] = false;

		}
		ladder_num = 1;
	}

}

void solve() {
    dfs(1, 1, 0);
    if (answer == INT_MAX)   cout << -1 << "\n";
    else cout << answer << "\n";
}

void input() {
    cin >> n >> m >> h;

    int a, b;
    while (m--) {
        cin >> a >> b;
        if (add_ladder(a, b)) ladder[a][b] = true;
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);  cout.tie(NULL);
    //freopen("input.txt", "r", stdin);

    input();
    solve();

    return 0;
}

피드백

이상, 초과 주의하자, 조건범위에 주의하자.
절대로 답이 될 수 없는 경우를 좀더 생각해 보자.
나의 경우 속도가 굉장히 맘에 안 들었었는데, 3일때의 가지치지를 안해서 그랬다.

개인적으로, 이문제를 푼뒤 바로 이문제를 풀어보는걸 추천한다

  • 연구소
  • 같은 삼성 기출문제 이고, 굉장히 유사한 문제이다.