Game Develop

[Algorithm] Baekjoon 15684번 : 사다리 조작 본문

Algorithm/Baekjoon

[Algorithm] Baekjoon 15684번 : 사다리 조작

MaxLevel 2023. 9. 26. 04:05

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

 

15684번: 사다리 조작

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

www.acmicpc.net

 
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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
int col, installCount, row;
bool visited[31][11] = { false };
int arr[31][11] = { 0 };
int maxIndex = 0;
int answer = -1;
 
bool checkInstallIsPossible(int y, int x)
{
    if (x == 1) // 첫 열
    {
        if (!visited[y][x] && !visited[y][x + 1]) return true;
        return false;
    }
    else if (x == col - 1) // 끝-1열
    {
        if (!visited[y][x] && !visited[y][x - 1]) return true;
        return false;
    }
    else // 가운데열들
    {
        if (!visited[y][x] && !visited[y][x - 1] && !visited[y][x + 1]) return true;
        return false;
    }
}
 
bool PlayGame()
{
    int count = 0;
    bool isBreak = false;
 
    for (int i = 1; i <= col; ++i)
    {
        int curY = 1;
        int curX = i;
        bool tempVisited[31][11] = { false };
 
        while (1)
        {
            if (arr[curY][curX] == 1)
            {
                if (!tempVisited[curY][curX + 1])
                {
                    tempVisited[curY][curX] = true;
                    ++curX;
                }
                else ++curY;
            }
            else if (arr[curY][curX] == -1)
            {
                if (!tempVisited[curY][curX-1])
                {
                    tempVisited[curY][curX] = true;
                    --curX;
                }
                else ++curY;
            }
            else if (arr[curY][curX] == 0)
            {
                ++curY;
            }
 
            if (curY == row + 1)
            {
                if (curX == i) ++count;
                else isBreak = true;
 
                break;
            }
        }
 
        if (isBreak) break;
    }
 
    return count == col;
}
 
void DFS(int index, int depth, int maxDepth) 
{
    if (depth == maxDepth)
    {
        bool result = PlayGame();
        if (result) answer = maxDepth;
        return;
    }
 
    for (int i = index+1; i < maxIndex; ++i) 
    {
        int curY = i / col + 1;
        int curX = i % col + 1;
 
        if (checkInstallIsPossible(curY, curX))
        {
            visited[curY][curX] = true;
            arr[curY][curX] = 1;
            arr[curY][curX + 1] = -1;
 
            DFS(i, depth+1, maxDepth);
 
            visited[curY][curX] = false;
            arr[curY][curX] = 0;
            arr[curY][curX + 1] = 0;
        }
 
        if (answer != -1) break;
    }
}
 
int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    cin >> col >> installCount >> row; 
 
    maxIndex = col * row - 1;
    for (int i = 0; i < installCount; ++i)
    {
        int a, b;
        cin >> a >> b; 
 
        visited[a][b] = true;
        arr[a][b] = 1;
        arr[a][b + 1] = -1;
    }
 
    if (installCount == 0 || PlayGame())
    {
        cout << 0;
        return 0;
    }
 
    for (int i = 1; i <= installCount; ++i)
    {
        if (i == 4) break;
 
        for (int j = 0; j < maxIndex; ++j) 
        {
            int curY = j / col + 1;
            int curX = j % col + 1;
 
            if (checkInstallIsPossible(curY, curX))
            {
                visited[curY][curX] = true;
                arr[curY][curX] = 1;
                arr[curY][curX + 1] = -1;
                DFS(j, 1, i);
                visited[curY][curX] = false;
                arr[curY][curX] = 0;
                arr[curY][curX + 1] = 0;
            }
 
            if (answer != -1) break;
        }
 
        if (answer != -1) break;
    }
 
    cout << answer;
}
 cs

일단 통과시켜보잔 마인드로 막 짜긴했는데... 통과시키고 나니 정말 볼품?없어 보인다.

visited도 사실 필요없어보이기도 하고.. 사실 이런 종류 문제는 코테때 안나왔으면 하기도하고, 사실 잘 나오지도 않는 것 같다.

그럼에도 불구하고 풀어는 봐야한다.

'Algorithm > Baekjoon' 카테고리의 다른 글

[Algorithm] Baekjoon 1722번 : 순열의 순서  (0) 2023.09.26
[Algorithm] Baekjoon 14499번 : 주사위 굴리기  (0) 2023.09.26
[Algorithm] Baekjoon 13397번 : 구간 나누기 2  (0) 2023.09.23
[Algorithm] Baekjoon 1025번 : 제곱수 찾기  (0) 2023.09.23
[Algorithm] Baekjoon 9079번 : 동전 게임  (0) 2023.09.22
'Algorithm/Baekjoon' Related Articles more