In [1]:
1
2
3
4
5
6
7
8
import sys, random
sys.path.append("/home/swyoo/algorithm/")
from utils.verbose import logging_time
from sys import stdin
from copy import deepcopy
from collections import defaultdict
from pprint import pprint
import numpy as np
15684. 사다리 조작
주어진 사다리의 격자 shape 는 $(n, h)$ 이며, input으로 $m$ 개의 위치에 사다리가 주어진다.
다음과 같이 사다리를 나타낸다.
1
2
j-th (j+1)-th ... j-th (j+1)-th ..
|_______| | ==> 1 0
우리의 목표는 사다리 수를 최소화 하여 j번째 열이사다리를 타고 내려와 최종적으로 j번째에 떨어지도록 조작할 것이다.
단, 조건은 다음과 같다.
- 만약, 정답이
3보다 큰 값이면-1을 출력한다. 또, 불가능한 경우에도-1을 출력한다.
이러한 조건으로 유추해 봤을때, 경우의 수를 enumerate해면서 목표를 구하는데 필요없는 부분은 pruning하는 문제 일 것이다.
Parse Data
사다리 representation 행렬 a는 다음과 같다.
입력은 번째 수 이므로 -1을 하여 index 처리한다.
In [2]:
1
2
3
4
5
6
7
8
9
10
plot = lambda a: print(np.array(a))
stdin = open('data/ladder.txt')
input = stdin.readline
n, m, h = list(map(int, input().split()))
a = [[0] * n for _ in range(h)]
ladders = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(m)]
for i, j in ladders:
a[i][j] = 1
plot(a)
1
2
3
4
5
6
7
[[1 0 0 0 0]
[0 0 1 0 0]
[0 1 0 0 0]
[0 0 0 0 0]
[1 0 0 1 0]
[0 0 0 0 0]]
Idea
- 사다리 놓을 수 있는 부분이 어디인지 파악하고, 사다리를 놓는 경우를 enumerate한다.
- DFS를 통해 enumerate (pruning, that is, backtracking will be used.)
- 사다리를 놓은뒤 각 경우마다 각 열마다 사다리를 내려와 j번째열이 j번째에 도달하는가 체크한다.
- 사다리를 내려오는 subroutine 구현 필요.
optimal substructure, overlapping subproblems property가 만족되지 않아 dynamic programming은 불가.
Step 1. 사다리 내려오기
각 열마다 사다리를 내려오는 subroutine을 구현하고, 체크함수 ladder만든다.
In [3]:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def go(y):
""" given y, global: h, n"""
x = 0
while 0 <= x < h:
if a[x][y] and 0 <= y + 1 < n and not a[x][y + 1]:
y += 1
elif not a[x][y] and 0 <= y - 1 < n and a[x][y - 1]:
y -= 1
x += 1
return y
plot(a)
print("after down:")
for i in range(n):
print(go(i), end=' ')
1
2
3
4
5
6
7
8
[[1 0 0 0 0]
[0 0 1 0 0]
[0 1 0 0 0]
[0 0 0 0 0]
[1 0 0 1 0]
[0 0 0 0 0]]
after down:
2 1 4 0 3
In [4]:
1
2
3
4
5
6
def ladder():
for i in range(n):
if i != go(i):
return False
return True
ladder()
1
False
Step 2. 사다리 놓기
2-2. points
사다리 놓을 수 있는 부분이 어디인지 파악한다.
points로 모아놓고 순차적으로 경우의 수를 파악하겠다.
다음 그림과 같이 사다리를 놓을 수 있는 부분은 파란색 동그라미(사다리 representation a에서는 1이 될 수 있는 부분)로 표시하였다.
i,j 에 사다리를 놓을 수 있으려면 인접한 부분이 0 이어야 한다.
In [5]:
1
2
3
4
5
6
7
8
9
10
11
12
points = []
for i in range(h):
for j in range(n - 1):
if a[i][j]: continue
flag = False
for jj in [k for k in [j - 1, j + 1] if 0 <= k < n]:
if a[i][jj]: flag = True
if flag: continue
points.append((i, j))
print(len(points))
print(points)
1
2
3
12
[(0, 2), (0, 3), (1, 0), (2, 3), (3, 0), (3, 1), (3, 2), (3, 3), (5, 0), (5, 1), (5, 2), (5, 3)]
2-3. enumerate
그런데 만약 points에서 idx번째에 사다리를 놓았을 경우, idx + 1 번째에는 사다리를 놓지 못할 수 있다
왜냐하면 두 가로선이 연속하거나 서로 접하면 안 된다는 조건이 있기 때문이다.
이 경우를 다음과 같이 구현할 것이다.
1
2
3
4
5
x, y = points[idx]
if idx + 1 < len(points) and (x == points[idx + 1][0]) and (points[idx + 1][1] - y == 1):
dfs(idx + 2, cnt + 1)
else:
dfs(idx + 1, cnt + 1)
따라서, 사다리를 놓는 경우를 dfs를 통해 eumerate 할 경우 다음과 같이 구현한다.
여기서 cnt는 놓은 사다리 수 이다.
주의해야할 점은 (사다리를 놓는 경우, 놓지 않는 경우) 각각 1번씩 꼭 call 해야한다.
(처음에 이걸 놓쳐서 많은 시간을 소비했다. Appendix에서 자세히 다루겠다.)
In [6]:
1
print(points)
1
2
[(0, 2), (0, 3), (1, 0), (2, 3), (3, 0), (3, 1), (3, 2), (3, 3), (5, 0), (5, 1), (5, 2), (5, 3)]
In [7]:
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
k = 0
def dfs(idx, cnt, selected):
global k
# print(selected) # cnt <= 4
if cnt == 4: # limit recursion at most |points| choose (4 - 1) cases after this line.
# print(selected) # distinct cases of cnt == 4
return
if idx == len(points): # this line is indispensible.
k += 1 # distinct cases of cnt <= 3
return
x, y = points[idx]
# case 1 - let a ladder at points[idx]
a[x][y] = 1
if idx + 1 < len(points) and (x == points[idx + 1][0]) and (points[idx + 1][1] - y == 1):
dfs(idx + 2, cnt + 1, selected + [idx]) # because points[idx + 1] is adjacent with points[idx], skip points[idx + 1]
else:
dfs(idx + 1, cnt + 1, selected + [idx])
a[x][y] = 0
# case 2 - skip letting the ladder at points[idx]
dfs(idx + 1, cnt, selected)
dfs(idx=0, cnt=0, selected=[])
print(k)
1
2
226
구현
따라서, 다음과 같이 구현한다.
백준 에 채점할 때는 pruning을 recursion중간에 하지 않으면 시간초과 가 뜬다.
따라서, 다음과 같이 pruning during recursion하는 코드들을 써야 통과할 수 있다.
1
2
3
4
5
6
7
8
9
10
if ans <= cnt: return # pruning during recursion
if ladder(): # pruning during recursion
ans = min(ans, cnt)
return
if cnt == 3: return # pruning by limitting the selection of 3 points.
if idx == len(points):
return
또한, Pypy3 로 해야 통과가 된다. (더 효율적인 알고리즘을 만들 필요가 있다. )
In [8]:
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
@logging_time
def solution(a, show=False):
h, n, INF = len(a), len(a[0]), 1e20
def go(y):
""" given y, global: h, n"""
x = 0
while 0 <= x < h:
if a[x][y] and 0 <= y + 1 < n and not a[x][y + 1]:
y += 1
elif not a[x][y] and 0 <= y - 1 < n and a[x][y - 1]:
y -= 1
x += 1
return y
def ladder():
for i in range(n):
if i != go(i):
return False
return True
points = []
for i in range(h):
for j in range(n - 1):
if a[i][j]: continue
flag = False
for jj in [k for k in [j - 1, j + 1] if 0 <= k < n]:
if a[i][jj]: flag = True
if flag: continue
points.append((i, j))
if show: print(points)
if not points: return 0 if ladder() else -1
ans = INF
snapshot = None
def dfs(idx, cnt):
nonlocal ans, snapshot
if ans <= cnt: return # pruning during recursion
if ladder(): # pruning during recursion
if show and cnt < ans: snapshot = deepcopy(a)
ans = min(ans, cnt)
return
if cnt == 3: return # pruning by limitting the selection of 3 points.
if idx == len(points):
return
x, y = points[idx]
a[x][y] = 1
if idx + 1 < len(points):
i, j = points[idx + 1]
if x == i and j - y == 1:
dfs(idx + 2, cnt + 1)
else:
dfs(idx + 1, cnt + 1)
else:
dfs(idx + 1, cnt + 1)
a[x][y] = 0
dfs(idx + 1, cnt)
dfs(idx=0, cnt=0)
if show: plot(snapshot)
return ans if ans != INF else -1
print(solution(a, show=True, verbose=True))
1
2
3
4
5
6
7
8
9
10
[(0, 2), (0, 3), (1, 0), (2, 3), (3, 0), (3, 1), (3, 2), (3, 3), (5, 0), (5, 1), (5, 2), (5, 3)]
[[1 0 1 0 0]
[0 0 1 0 0]
[0 1 0 1 0]
[0 1 0 0 0]
[1 0 0 1 0]
[0 0 0 0 0]]
WorkingTime[solution]: 1.15156 ms
3
Test Cases
제대로 구현했나 check하기 위해 test data를 generate하는 함수 구현.
In [9]:
1
2
3
4
5
6
7
8
9
10
11
12
## Generate Test data
def generate(n, h):
a = [[0] * n for _ in range(h)]
for i in range(h):
if random.randint(0, 10) % 2:
for j in random.choices(range(1, n - 1, 3), k=random.randint(0, n//2)):
a[i][j] = 1
else:
for j in random.choices(range(0, n - 1, 3), k=random.randint(0, n//2)):
a[i][j] = 1
return a
generate(n, h)
1
2
3
4
5
6
[[0, 0, 0, 0, 0],
[0, 0, 0, 1, 0],
[0, 0, 0, 1, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 1, 0],
[0, 0, 0, 1, 0]]
Discuss
rebas’s blog 의 코드는 다음과 같다. 내 코드보다 약간 더 빠른 것같다.
시간 복잡도는 동일하지만, 이유는 다음과 같다.
- 사다리를 타고 내려오는
ladder()함수가 조금 더 빠르다. - 사다리를 놓을 수 있는 지점들
points를 찾아놓고 enumerate하지 않고
곧바로 enumerate하기때문에 overhead가 준다.
In [10]:
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
@logging_time
def another(a, show=False):
h, n, INF = len(a), len(a[0]), 1e20
def ladder():
for i in range(n):
k = i
for j in range(h): # (j, k) will be a cursor.
if a[j][k]:
k += 1
elif k > 0 and a[j][k-1]:
k -= 1
if i != k:
return False
return True
ans = 4
snapshot = None
def solve(cnt, x, y):
nonlocal ans, snapshot
if ans <= cnt:
return
if ladder():
if show and cnt < ans: snapshot = deepcopy(a)
ans = min(ans, cnt)
return
if cnt == 3:
return
for i in range(x, h):
k = y if i == x else 0
for j in range(k, n-1):
if a[i][j]: # skip
j += 1
else:
a[i][j] = 1
solve(cnt+1, i, j+2)
a[i][j] = 0
solve(0, 0, 0)
if show: plot(snapshot)
return ans if ans < 4 else -1
another(a, show=True, verbose=True)
1
2
3
4
5
6
7
8
[[1 0 1 0 0]
[0 0 1 0 0]
[0 1 0 1 0]
[0 1 0 0 0]
[1 0 0 1 0]
[0 0 0 0 0]]
WorkingTime[another]: 1.24741 ms
1
3
Mycode vs Another
In [11]:
1
2
3
4
5
6
7
8
9
10
11
12
a = [[0] * n for _ in range(h)]
for i in range(h):
if random.randint(0, 10) % 2:
for j in random.choices(range(1, n - 1, 3), k=random.randint(0, n//2)):
a[i][j] = 1
else:
for j in random.choices(range(0, n - 1, 3), k=random.randint(0, n//2)):
a[i][j] = 1
plot(a)
ans1 = solution(a, show=True, verbose=True)
ans2 = another(a, show=True, verbose=True)
ans1, ans2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
[[0 0 0 1 0]
[0 0 0 0 0]
[1 0 0 0 0]
[0 1 0 0 0]
[0 0 0 0 0]
[0 0 0 0 0]]
[(0, 0), (0, 1), (1, 0), (1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3), (4, 0), (4, 1), (4, 2), (4, 3), (5, 0), (5, 1), (5, 2), (5, 3)]
[[1 0 0 1 0]
[0 0 0 1 0]
[1 0 0 0 0]
[0 1 0 0 0]
[0 1 0 0 0]
[0 0 0 0 0]]
WorkingTime[solution]: 2.28500 ms
[[1 0 0 1 0]
[0 0 0 1 0]
[1 0 0 0 0]
[0 1 0 0 0]
[0 1 0 0 0]
[0 0 0 0 0]]
WorkingTime[another]: 0.94986 ms
1
(3, 3)
In [12]:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
""" sanity checks. """
for _ in range(3):
n, h = 5, 6
a = [[0] * n for _ in range(h)]
for i in range(h):
if random.randint(0, 10) % 2:
for j in random.choices(range(1, n - 1, 3), k=random.randint(0, n//2)):
a[i][j] = 1
else:
for j in random.choices(range(0, n - 1, 3), k=random.randint(0, n//2)):
a[i][j] = 1
# plot(a)
ans1 = solution(a, show=False, verbose=True)
ans2 = another(a, verbose=True)
assert ans1 == ans2, "{} vs {}| {}".format(ans1, ans2, a)
print(ans1, ans2)
1
2
3
4
5
6
7
8
9
10
WorkingTime[solution]: 0.59271 ms
WorkingTime[another]: 0.81420 ms
2 2
WorkingTime[solution]: 0.05865 ms
WorkingTime[another]: 0.03052 ms
1 1
WorkingTime[solution]: 0.42868 ms
WorkingTime[another]: 0.70071 ms
1 1
Submitted Code
In [13]:
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
from sys import stdin
stdin = open('data/ladder.txt')
input = stdin.readline
n, m, h = list(map(int, input().split()))
a = [[0] * n for _ in range(h)]
ladders = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(m)]
for i, j in ladders:
a[i][j] = 1
def solution(a):
h, n, INF = len(a), len(a[0]), 1e20
def go(y):
x = 0
while 0 <= x < h:
if a[x][y] and 0 <= y + 1 < n and not a[x][y + 1]:
y += 1
elif not a[x][y] and 0 <= y - 1 < n and a[x][y - 1]:
y -= 1
x += 1
return y
def ladder():
for i in range(n):
if i != go(i):
return False
return True
points = []
for i in range(h):
for j in range(n - 1):
if a[i][j]: continue
flag = False
for jj in [k for k in [j - 1, j + 1] if 0 <= k < n]:
if a[i][jj]: flag = True
if flag: continue
points.append((i, j))
if not points: return 0 if ladder() else -1
ans = INF
def dfs(idx, cnt):
nonlocal ans
if ans <= cnt:
return
if ladder():
ans = min(ans, cnt)
return
if cnt == 3:
return
if idx == len(points): return
x, y = points[idx]
a[x][y] = 1
if idx + 1 < len(points) and (x == points[idx + 1][0]) and (points[idx + 1][1] - y == 1):
dfs(idx + 2, cnt + 1)
else:
dfs(idx + 1, cnt + 1)
a[x][y] = 0
dfs(idx + 1, cnt)
dfs(idx=0, cnt=0)
return ans if ans != INF else -1
print(solution(a))
1
2
3
In [14]:
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
from sys import stdin
from itertools import combinations
stdin = open('data/ladder.txt')
input = stdin.readline
n, m, h = list(map(int, input().split()))
a = [[0] * n for _ in range(h)]
ladders = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(m)]
for i, j in ladders:
a[i][j] = 1
def solution(a):
h, n, INF = len(a), len(a[0]), 1e20
def go(y):
x = 0
while 0 <= x < h:
if a[x][y] and 0 <= y + 1 < n and not a[x][y + 1]:
y += 1
elif not a[x][y] and 0 <= y - 1 < n and a[x][y - 1]:
y -= 1
x += 1
return y
def ladder():
for i in range(n):
if i != go(i):
return False
return True
points = []
for i in range(h):
for j in range(n - 1):
if a[i][j]: continue
flag = False
for jj in [k for k in [j - 1, j + 1] if 0 <= k < n]:
if a[i][jj]: flag = True
if flag: continue
points.append((i, j))
if not points: return 0 if ladder() else -1
ans = INF
for i in range(4):
for selected in list(combinations(range(len(points)), i)):
for k in selected: a[points[k][0]][points[k][1]] = 1
if ladder():
ans = min(ans, i)
for k in selected: a[points[k][0]][points[k][1]] = 0
return ans if ans != INF else -1
print(solution(a))
1
2
3
Appendix. consideration
All combination cases can be found as follows.
${3 \choose 0} + {3 \choose 1} + {3 \choose 2} + {3 \choose 3} = 8$
In [15]:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
indices = list(range(3))
c1 = c2 = c3 = k = 0
def dfs(idx, selected):
global c1, c2, c3, k
# print(selected) # recursion 중에 똑같은 selected 여러번 불릴 수 있다.
if len(selected) == 1: c1 += 1 # 이 시점에 return하면 distinct한 5C1을 구할 수 있다.
if len(selected) == 2: c2 += 1 # 이 시점에 return하면 distinct한 5C2을 구할 수 있다.
if len(selected) == 3: c3 += 1 # 이 시점에 return하면 distinct한 5C3을 구할 수 있다.
if idx == len(indices):
k += 1
print(selected, end=' ') # distintive한 cases들을 출력가능.
return
dfs(idx + 1, selected + [idx])
dfs(idx + 1, selected)
dfs(idx=0, selected=[])
c1, c2, c3, k
1
[0, 1, 2] [0, 1] [0, 2] [0] [1, 2] [1] [2] []
1
(6, 4, 1, 8)
Partial combinations
Partial combinations can be found by limiting as follows.
1
2
if len(selected) == 4:
return
${4 \choose 0} + {4 \choose 1} + {4 \choose 2} + {4 \choose 3} = 15$
In [16]:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
indices = list(range(4))
k = 0
def dfs(idx, selected):
global k
# print(selected) # recursion 중에 똑같은 selected 여러번 불릴 수 있다.
if len(selected) == 4:
return
if idx == len(indices):
k += 1
print(selected, end=' ')
return
dfs(idx + 1, selected + [idx])
dfs(idx + 1, selected)
dfs(idx=0, selected=[])
k
1
[0, 1, 2] [0, 1, 3] [0, 1] [0, 2, 3] [0, 2] [0, 3] [0] [1, 2, 3] [1, 2] [1, 3] [1] [2, 3] [2] [3] []
1
15
Use Libary
In [17]:
1
2
3
4
5
from itertools import permutations, combinations
n = 3
for i in range(n + 1):
for x in list(combinations(range(n), i)):
print(x, end=' ')
1
() (0,) (1,) (2,) (0, 1) (0, 2) (1, 2) (0, 1, 2)
In [18]:
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
@logging_time
def solution2(a, show=False):
h, n, INF = len(a), len(a[0]), 1e20
def ladder():
for i in range(n):
k = i
for j in range(h):
if a[j][k]:
k += 1
elif k > 0 and a[j][k-1]:
k -= 1
if i != k:
return False
return True
points = []
for i in range(h):
for j in range(n - 1):
if a[i][j]: continue
flag = False
for jj in [k for k in [j - 1, j + 1] if 0 <= k < n]:
if a[i][jj]: flag = True
if flag: continue
points.append((i, j))
if show: print(points)
if not points: return 0 if ladder() else -1
ans = INF
snapshot = None
for i in range(4):
for selected in list(combinations(range(len(points)), i)):
for k in selected: a[points[k][0]][points[k][1]] = 1
if ladder():
if show and i < ans: snapshot = deepcopy(a)
ans = min(ans, i)
for k in selected: a[points[k][0]][points[k][1]] = 0
if show: plot(a)
return ans if ans != INF else -1
In [22]:
1
2
3
4
5
6
7
8
9
10
11
n, h = 10, 8
a = [[0] * n for _ in range(h)]
for i in range(h):
if random.randint(0, 10) % 2:
for j in random.choices(range(1, n - 1, 3), k=random.randint(0, n//2)):
a[i][j] = 1
else:
for j in random.choices(range(0, n - 1, 3), k=random.randint(0, n//2)):
a[i][j] = 1
plot(a)
print(solution2(a, show=True, verbose=True))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
[[0 0 0 0 0 0 0 0 0 0]
[0 1 0 0 1 0 0 1 0 0]
[0 0 0 0 1 0 0 1 0 0]
[1 0 0 1 0 0 1 0 0 0]
[0 1 0 0 1 0 0 1 0 0]
[1 0 0 0 0 0 0 0 0 0]
[0 0 0 0 1 0 0 1 0 0]
[0 0 0 1 0 0 1 0 0 0]]
[(0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (0, 6), (0, 7), (0, 8), (2, 0), (2, 1), (2, 2), (3, 8), (5, 2), (5, 3), (5, 4), (5, 5), (5, 6), (5, 7), (5, 8), (6, 0), (6, 1), (6, 2), (7, 0), (7, 1), (7, 8)]
[[0 0 0 0 0 0 0 0 0 0]
[0 1 0 0 1 0 0 1 0 0]
[0 0 0 0 1 0 0 1 0 0]
[1 0 0 1 0 0 1 0 0 0]
[0 1 0 0 1 0 0 1 0 0]
[1 0 0 0 0 0 0 0 0 0]
[0 0 0 0 1 0 0 1 0 0]
[0 0 0 1 0 0 1 0 0 0]]
WorkingTime[solution2]: 8.08096 ms
2
Leave a comment