브루트 포스

사다리 조작

4gats 2023. 9. 10. 12:52

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

 

15684번: 사다리 조작

사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선

www.acmicpc.net

배열을 조작하면서 개수가 늘어가는 브루트포스

재귀를 쓰는 문제는 문제에서 티를 낸다.

만약, 정답이 3보다 큰 값이면 -1을 출력.

즉, 추가 가로줄 3개까지만 dfs를 돌리면 된다.

 

 

처음에는 

b번 세로선과 b+1번 세로선을 a번 점선 위치에서 연결했다는 의미

이 조건을 보고 

map[a][b] = true;

map[a][b + 1] = true;

입력을 이렇게 줬다. 

 

a,b가 (1,1), (1,3) 이렇게 들어왔다고 가정하면

map[1][1], map[1][2], map[1][3], map[1][4]

모두 true가 된다.

2,3이 연결되어 있지않은데도!

연결되게 된다...

그러므로 입력을 바꿔야한다!

 

map[a][b] = true이면

(a, b), (a, b + 1)에 사다리 존재

 

2. dfs 함수

브루트 포스는 true로 만들었다면 false로 다시 바꿔줘야한다.

단, 두 가로선이 연속하거나 서로 접하면 안 된다.

조건을 구현하며 dfs를 하면 된다.

if (map[i][j] || map[i][j - 1] || map[i][j + 1])
                continue;

 

<소스 코드>

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
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
 
using namespace std;
 
bool map[34][15];
int n, m, h;
 
int ans = 987654321;
 
// 똑같은 번호로 가는지 확인하는 함수
bool play()
{
    for (int j = 1; j <= n; j++)
    {
        int cur = j;
        for (int i = 1; i <= h; i++)
        {
            // -> 사다리
            if (map[i][cur])
                cur++;
            // <- 사다리
            else if (map[i][cur - 1])
                cur--;
        }
 
        if (cur != j)
            return false;
    }
    return true;
}
 
// 사다리 놓기
void dfs(int genkai, int cnt)
{
    // 0일땐 바로 이거 해보겠지
    if (genkai == cnt)
    {
        if (play())
        {
            cout << genkai << '\n';
            exit(0);
        }
        return;
    }
 
    for (int j = 1; j < n; j++)
    {
        for (int i = 1; i <= h; i++)
        {
            // 사다리가 존재
            // 왼, 오에 사다리 존재하는데 놓으면 2연 사다리가 되니까
            if (map[i][j] || map[i][j - 1] || map[i][j + 1])
                continue;
 
            // 브루트포스 켰으면 꺼준다
            map[i][j] = true;
            dfs(genkai, cnt + 1);
            map[i][j] = false;
 
            // 왼쪽 오른쪽에 사다리가 없으면 그냥 내려간다
            // 이거 안넣어주면 시간 초과!
            while (!map[i][j - 1] && !map[i][j + 1])
                i++;
        }
    }
    return;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    memset(map, false, sizeof(map));
 
    cin >> n >> m >> h;
    for (int i = 0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;
        map[a][b] = true;
    }
 
    // 정답이 3보다 크면 -1 출력
    // 추가 가로줄 0개부터 3개까지만 dfs
    for (int i = 0; i < 4; i++)
    {
        dfs(i, 0);
    }
 
    if (ans == 987654321)
        ans = -1;
    cout << ans << '\n';
 
    return 0;
}
 
 cs
 

시간 초과!!!

while (!map[i][j - 1] && !map[i][j + 1])
 
                i++;
 
이거 안넣어주면 시간 초과 나온다!!