8000 Update 15684.cpp · JeeeunOh/basic-algo-lecture@016e9a1 · GitHub
[go: up one dir, main page]
Skip to content

Commit 016e9a1

Browse files
encrypted-defencrypted-def
authored
Update 15684.cpp
1 parent 8057d96 commit 016e9a1

File tree

1 file changed

+32
-28
lines changed

1 file changed

+32
-28
lines changed

‎0x0D/solutions/15684.cpp

Lines changed: 32 additions & 28 deletions
Original file line numberDiff line numberDiff line change
@@ -1,8 +1,9 @@
11
// Authored by : SciEm
2-
// Co-authored by : -
3-
// http://boj.kr/86f2dbc3aaf549e1a41a104623c74e6a
2+
// Co-authored by : BaaaaaaaaaaarkingDog
3+
// http://boj.kr/74da3b10100849d68340661e3e748159
44
#include <bits/stdc++.h>
55
using namespace std;
6+
67
#define X first
78
#define Y second
89

@@ -17,35 +18,13 @@ bool check() {
1718
int cur = j;
1819
for (int i = 1; i <= h; i++) {
1920
if (ladder[i][cur - 1]) cur--;
20-
else if (ladder[i][cur]) cur++;
21+
else if (ladder[i][cur]) cur++;
2122
}
2223
if (cur != j) return false;
2324
}
2425
return true;
2526
}
2627

27-
void backtracking(int l, int k) {
28-
if (k == l) {
29-
if (check()) {
30-
cout << l;
31-
exit(0);
32-
}
33-
return;
34-
}
35-
int st = 0;
36-
if (k) {
37-
if (coords[idxs[k - 1]].Y == n - 1) // 이전 선택이 마지막 열이면
38-
st = idxs[k - 1] + 1; // 그 다음 좌표(다음 행, 첫 열)부터 시작해도 인접하지 않음
39-
else st = idxs[k - 1] + 2; // 아니면 다다음 좌표부터
40-
}
41-
for (int i = st; i < coords.size(); i++) {
42-
idxs[k] = i;
43-
ladder[coords[i].X][coords[i].Y] = true;
44-
backtracking(l, k + 1);
45-
ladder[coords[i].X][coords[i].Y] = false;
46-
}
47-
}
48-
4928
int main() {
5029
ios::sync_with_stdio(0);
5130
cin.tie(0);
@@ -64,7 +43,32 @@ int main() {
6443
coords.push_back({i, j});
6544
}
6645

67-
for (int l = 0; l <= 3; l++)
68-
backtracking(l, 0);
69-
cout << -1;
46+
47+
if(check()){
48+
cout << 0;
49+
return 0;
50+
}
51+
52+
int ans = 0x7f7f7f7f;
53+
int sz = coords.size();
54+
for(int i = 0; i < sz; i++){
55+
ladder[coords[i].X][coords[i].Y] = true;
56+
if(check()) ans = min(ans, 1);
57+
for(int j = i+1; j < sz; j++){
58+
ladder[coords[j].X][coords[j].Y] = true;
59+
if(check()) ans = min(ans, 2);
60+
for(int k = j+1; k < sz; k++){
61+
ladder[coords[k].X][coords[k].Y] = true;
62+
if(check()) ans = min(ans, 3);
63+
ladder[coords[k].X][coords[k].Y] = false;
64+
}
65+
ladder[coords[j].X][coords[j].Y] = false;
66+
}
67+
ladder[coords[i].X][coords[i].Y] = false;
68+
}
69+
if(ans == 0x7f7f7f7f) ans = -1;
70+
cout << ans;
7071
}
72+
/*
73+
3중 for문 대신 백트래킹을 써도 됨
74+
*/

0 commit comments

Comments
 (0)
0