https://www.acmicpc.net/problem/15684
15684번: 사다리 조작
사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선이 같은 위치를 갖는다. 아래 그림은 N = 5, H = 6 인 경우의 그림이고, 가로선은 없다. 초록선은 세로선을 나타내고, 초록선과 점선이 교차하는 점은 가로선을 놓을 수 있는 점이다. 가로선은 인접한 두 세로선을 연결해야 한다. 단, 두 가로선이 연속하거나 서로
www.acmicpc.net
사실 구현자체는 어렵지 않았는데 시간초과가 계속 나서 한참 고생했던 문제이다...
먼저 문제에서 3개 넘게 사용해야하는 경우에는 -1을 출력하라고 했으므로
가로선을 놓는 모든 경우를 탐색해줄 수 있긴하지만 백트래킹을 잘해줘야한다...ㅠㅠ
내 기준 이 문제에서 중요한 부분!
1. 가로선을 놓을 때 나는 가로선의 시작점을 1로 놓고 끝점을 2(빈 곳은 0)로 놓았다.
단순히 true/false로 놓으면 왼쪽으로 가는지 오른쪽으로 가는지를 다시 알아내야하기 때문이다.
이 아이디어는 사실 다른 곳에서 본거다ㅎㅎ
2. 사다리 타기를 시작할 때, 왼쪽이나 오른쪽으로 열을 이동하는 경우에도 한칸을 내려가도록 해줘야한다.
그렇지 않다면 가로선에서 계속 오른쪽 왼쪽을 왔다갔다하는 무한 루프에 빠질 수 있다.
3. 시간 초과를 해결하기 위한 가장 중요한 부분인데, 가로선을 놓을 곳을 탐색할 때 다시 (1,1)부터 하면 안되고 현재 가로선을 놓아준 행부터 다시 탐색을 시작하도록 현재 행을 매개변수로 넘겨준다.
4. 마지막으로 개인적으로 실수했던 부분인데 1개만 놓는 경우, 2개를 놓는 경우, 3개를 놓는 경우를 각각 해줬었다.
2개를 놓는 경우는 1개를 놓은 상태에서 하나 더 놓아주면 되는데 바보같은 짓을 했다..
|
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
|
#include <iostream>
#include <vector>
using namespace std;
int n, m, h;
int check[32][11];
bool ispossible() {
//모든 세로선에 대해서 검사
for (int i = 1; i <= n; i++) {
int x = 0;
int y = i;
//사다리 타기 시작
while (true) {
//맨 밑에 도착
if (x == h + 1) {
//i번의 결과가 i번이면 break후 에 다음 세로선을 검사
//그렇지 않은 경우에는 바로 false를 리턴
if (y == i) break;
else return false;
}
//1인 경우에는 오른쪽사다리로 이동
if (check[x + 1][y] == 1) {
y++;
}//2인 경우는 왼쪽사다리로 이동
else if (check[x + 1][y] == 2) {
y--;
}
//한칸 내려간다.
x++;
}
}
return true;
}
int select(int x, int index) {
//3을 넘어가면 바로 -1을 리턴
if (index > 3) {
return -1;
}
int ans = -1;
//x행부터 탐색을 시작
for (int i = x; i <= h; i++) {
for (int j = 1; j < n; j++) {
if (check[i][j] != 0) continue;
if (check[i][j + 1] != 0) continue;
//i행의 j번과 j+1번에 가로선을 놓는다.
check[i][j] = 1;
check[i][j + 1] = 2;
//가로선을 놓은 상태에서 사다리 게임의 결과를 바로 확인
if (ispossible()) {
//i번 세로선이 i번에 도착한다면 현재 index(사용한 가로선 수)를 ans에 저장
ans = index;
}
//현재 가로선을 놓은 상태에서 추가로 다른 곳에 하나 더 놓는 경우를 탐색
//다음 탐색에서는 i행부터 진행한다.
int tmp = select(i, index + 1);
//ans가 초기값이라면 다음 탐색에서 받아온 tmp를 저장
if (ans == -1) ans = tmp;
//다른 곳에 가로선을 놓는 경우를 위해서 다시 가로선을 없애준다.
check[i][j] = 0;
check[i][j + 1] = 0;
}
}
return ans;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m >> h;
int a, b;
//가로선의 왼쪽점을 1, 오른쪽점을 2로 놓는다.
for (int i = 0; i < m; i++) {
cin >> a >> b;
check[a][b] = 1;
check[a][b + 1] = 2;
}
//가로선을 추가로 놓지않고 가능하다면 바로 0을 출력
if (ispossible()) cout << 0 << '\n';
else {
cout << select(1, 1) << '\n';
}
return 0;
}
Colored by Color Scripter
|