백준 15684. 사다리 조작

승케이 2019. 4. 11. 10:27

15684번: 사다리 조작

사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선이 같은 위치를 갖는다. 아래 그림은 N = 5, H = 6 인 경우의 그림이고, 가로선은 없다. 초록선은 세로선을 나타내고, 초록선과 점선이 교차하는 점은 가로선을 놓을 수 있는 점이다. 가로선은 인접한 두 세로선을 연결해야 한다. 단, 두 가로선이 연속하거나 서로

www.acmicpc.net

이 문제는 완전탐색 문제입니다.

탐색해야 될 경우의 수도 많지 않고 깊이도 깊지 않기 때문에 DFS를 활용한 완전탐색을 통해 문제를 해결했습니다.

사다리를 어떻게 표현하는 지도 중요한데 저는 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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105

#include<iostream>
 
using namespace std;
int n, m, h;
int ladder[32][12];
 
int blank_x[300];
int blank_y[300];
int blank_top = 0;
 
int minimum = 4;
 
int search(int x) { // x열 사다리 타기
    int goal = x;
 
    for (int i = 1; i <= h; i++) {
        int tmp = x;
 
        if (ladder[i][tmp] == 1)
            x++;
        else if (ladder[i][tmp - 1] == 1)
            x--;
    }
 
    if (x == goal) {
        return 1;
    }
 
    return 0;
}
int simul_all() {
    for (int i = 1; i <= n; i++) {
        if (search(i) == 0) {
            return 0;
        }
    }
    return 1;
}
int side_check(int x, int y) { // 양 옆 사다리 체크
    if (ladder[y][x - 1] == 1 || ladder[y][x + 1] == 1)
        return 0;
 
    return 1;
}
 
void dfs(int start, int sum) {
    if (sum >= minimum) // 가지치기 최소 사다리 개수보다 많으면 탐색 X
        return;
    else{
        for (int i = start; i < blank_top; i++) {
            int x = blank_x[i];
            int y = blank_y[i];
 
            if (side_check(x, y) == 1) {
                ladder[y][x] = 1;
 
                if (simul_all() == 1) {
                    minimum = sum;
                    ladder[y][x] = 0;
                    return;
                }
                else {
                    dfs(i + 1, sum + 1);
                    ladder[y][x] = 0;
                }
            }
        }
    }
 
}
int main() {
    cin >> n >> m >> h;
 
    for (int i = 0; i < m; i++) {
        int a, b;
 
        cin >> a >> b;
 
        ladder[a][b] = 1;
    }
 
    if (simul_all() == 1) { // 사다리를 추가하지 않은 상태를 탐색
        cout << "0" << endl;
        return 0;
    }
 
    for (int i = 1; i <= h; i++) { // 빈공간(탐색구간)을 스택에 쌓음
        for (int j = 1; j < n; j++) {
            if (ladder[i][j] == 0) {
                if (side_check(j, i) == 1) { // 양 옆에 사다리가 있는 지 판단
                    blank_x[blank_top] = j;
                    blank_y[blank_top++] = i;
                }
            }
        }
    }
 
    dfs(0, 1);
 
    if (minimum == 4)
        cout << "-1" << endl;
    else
        cout << minimum << endl;
 
}
" target="_blank" style="color:#4f4f4f; text-decoration:none">Colored by Color Scripter

열의 범위를 1부터 n까지 설정하고 ladder를 표현하는 2차원 배열의 범위는 0부터 n+1이상 까지 생성해줬기 때문에 따로 x열을 사다리 태울 때, 범위를 체크할 필요가 없었습니다.

의견이 있으시거나 수정해야할 부분이 있으면 편하게 공유 부탁드립니다!

저작자표시 비영리 동일조건 (새창열림)