In [1]:
1
2
3
4
5
6
7
import sys, random
sys.path.append("/home/swyoo/algorithm/")
from utils.verbose import logging_time
from utils.generator import random2D
from sys import stdin
from copy import deepcopy
import numpy as np
15683. 감시
다음과 같이 5가지의 cctv 종류가 있다.
주어진 격자의 shape 는 $n, m$. 이때, 벽은 $6$, cctv 종류는 $1, 2, 3, 4, 5$.
주어진 cctv 위치에 대해 사각지대에 속한 범위의 크기를 구하라.
cctv를 통해 감시할 수 있는 최대 범위 $|scope|^*$ 를 바탕으로 구하면 된다.
In [2]:
1
2
3
4
5
6
7
plot = lambda a: print(np.array(a))
stdin = open('data/monitor.txt')
input = stdin.readline
n, m = list(map(int, input().split()))
a = [list(map(int, input().split())) for _ in range(n)]
up, down, left, right = (-1, 0), (1, 0), (0, -1), (0, 1)
plot(a)
1
2
3
4
5
6
7
[[0 0 0 0 0 0]
[0 2 0 0 0 0]
[0 0 0 0 6 0]
[0 6 0 0 2 0]
[0 0 0 0 0 0]
[0 0 0 0 0 5]]
Idea
- cctv의 종류에 따라 감시할 수 있는 구간이 다르므로 종류에 따라 이를 enumerate 할수 있도록 구현하자.
- cctv 의 위치를 순서대로 DFS 하면서 감시 가능한 곳은 marking하자.
- 최종적으로 모든 cctv를 marking했을 경우에 대해 최대 감시 범위를 저장한다.
주의사항:
DFS 방식으로 감시구간을 enumerate하는 과정에서 marking에 주의해야한다.
서로 다른 cctv의 감시 구간이 겹칠수가있는데,
두 cctv 중 어느 하나라도 보고있는 경우, 감시 구간에 포함된다.
예를 들면, 밑의 그림과 같이 (0, 3)은 두 cctv에 의해 구간이 겹친다.
1
2
3
4
1 # # # # 1 # # # #
0 0 0 # 0 ---> 0 0 0 # 0
0 0 0 2 0 0 0 0 2 0
0 0 0 # 0 0 0 0 # 0
그리고, 2 cctv가 다른 방향을 볼경우, 위의 그림에서 오른쪽과 같다.
즉, 2의 감시방향을 (위,아래) 에서 (왼쪽, 오른쪽)으로 바꿀 경우, 1의 감시 구간에는 영향끼치면 안된다.
따라서, 겹치는 구간에 대해 영향관계를 고려하기 위해 감시하는 구간에 대해
marking을 -1 씩 감소하고, 되돌릴 경우 +1 씩 증가시킨다. (문제푸는데 이걸 생각해내는데 꽤 오래걸렸다.)
1
2
3
4
1 -1 -1 -2 -1 1 -1 -1 -1 -1
0 0 0 -1 0 ---> 0 0 0 0 0
0 0 0 2 0 -1 -1 -1 2 -1
0 0 0 -1 0 0 0 0 0 0
Step1. 감시 구현
각 cctv 종류 별로 감시하는 방법이 다르므로 이를 구현.
In [3]:
1
2
3
cctv = [(i, j) for i in range(n) for j in range(m) if a[i][j] and a[i][j] != 6]
cset = set([1,2,3,4,5])
cctv # cctv 위치
1
[(1, 1), (3, 4), (5, 5)]
In [4]:
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
def mark(x, y, dx, dy, fill):
i, j = x, y
x, y = x + dx, y + dy
while (0 <= x < n and 0 <= y < m):
if a[x][y] == 6: return
if a[x][y] not in cset:
a[x][y] += fill
x, y = x + dx, y + dy
def markAll(x, y, delta, kind, fill):
if kind == 1:
mark(x, y, *delta, fill)
elif kind == 2 or kind == 3:
mark(x, y, *delta[0], fill), mark(x, y, *delta[1], fill)
if kind == 4:
mark(x, y, *delta[0], fill), mark(x, y, *delta[1], fill), mark(x, y, *delta[2], fill)
if kind == 5:
mark(x, y, *delta[0], fill), mark(x, y, *delta[1], fill)
mark(x, y, *delta[2], fill), mark(x, y, *delta[3], fill)
directions = \
{1: [up, down, left, right],
2: [(up, down), (left, right)],
3: [(up, right), (right, down), (down, left), (left, up)],
4: [(left, up, right), (up, right, down), (right, down, left), (down, left, up)],
5: [(up, down, left, right)]}
a = random2D(shape=(n, m), sampling=[0, 1, 2, 3, 4, 5, 6], weights=[0.7, 0.05, 0.05, 0.05 ,0.05, 0.05, 0.05])
plot(a)
cctv = [(i, j) for i in range(n) for j in range(m) if a[i][j] and a[i][j] != 6]
print("indices of cctv:",cctv)
cidx = random.randint(0, len(cctv) - 1)
i, j = cctv[cidx]
print("cctv[{}]'s kind={}".format(cidx, a[i][j]))
delta = directions[a[i][j]][random.randint(0, len(directions[a[i][j]]) - 1)]
print(delta)
markAll(i, j, delta, kind=a[i][j], fill=-1) # 1 씩 감소
plot(a)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
[[0 0 0 0 0 3]
[5 5 0 0 0 0]
[2 6 0 0 0 0]
[0 0 2 1 0 0]
[0 0 1 0 0 3]
[2 1 1 1 0 0]]
indices of cctv: [(0, 5), (1, 0), (1, 1), (2, 0), (3, 2), (3, 3), (4, 2), (4, 5), (5, 0), (5, 1), (5, 2), (5, 3)]
cctv[3]'s kind=2
((-1, 0), (1, 0))
[[-1 0 0 0 0 3]
[ 5 5 0 0 0 0]
[ 2 6 0 0 0 0]
[-1 0 2 1 0 0]
[-1 0 1 0 0 3]
[ 2 1 1 1 0 0]]
In [5]:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def monitor(i, j, kind, fill):
for dij in directions[kind]:
markAll(i, j, dij, kind, fill)
yield dij
a = random2D(shape=(n, m), sampling=[0, 1, 2, 3, 4, 5, 6], weights=[0.7, 0.05, 0.05, 0.05 ,0.05, 0.05, 0.05])
plot(a)
cctv = [(i, j) for i in range(n) for j in range(m) if a[i][j] and a[i][j] != 6]
print("indices of cctv:",cctv)
cidx = random.randint(0, len(cctv) - 1)
i, j = cctv[cidx]
print("cctv[{}]=a[{}][{}]'s kind={}".format(cidx, i, j, a[i][j]))
for delta in monitor(i, j, kind=a[i][j], fill=-1):
plot(a)
markAll(i, j, delta, kind=a[i][j], fill=1) # plus 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
[[0 2 0 0 0 0]
[0 0 6 0 0 5]
[0 0 0 0 1 2]
[0 0 0 4 0 0]
[3 4 0 5 1 0]
[4 0 0 0 0 0]]
indices of cctv: [(0, 1), (1, 5), (2, 4), (2, 5), (3, 3), (4, 0), (4, 1), (4, 3), (4, 4), (5, 0)]
cctv[8]=a[4][4]'s kind=1
[[ 0 2 0 0 -1 0]
[ 0 0 6 0 -1 5]
[ 0 0 0 0 1 2]
[ 0 0 0 4 -1 0]
[ 3 4 0 5 1 0]
[ 4 0 0 0 0 0]]
[[ 0 2 0 0 0 0]
[ 0 0 6 0 0 5]
[ 0 0 0 0 1 2]
[ 0 0 0 4 0 0]
[ 3 4 0 5 1 0]
[ 4 0 0 0 -1 0]]
[[ 0 2 0 0 0 0]
[ 0 0 6 0 0 5]
[ 0 0 0 0 1 2]
[ 0 0 0 4 0 0]
[ 3 4 -1 5 1 0]
[ 4 0 0 0 0 0]]
[[ 0 2 0 0 0 0]
[ 0 0 6 0 0 5]
[ 0 0 0 0 1 2]
[ 0 0 0 4 0 0]
[ 3 4 0 5 1 -1]
[ 4 0 0 0 0 0]]
Step2. DFS
각 cctv 의 감시 경우의 수를 enumerate하면서 최대 감시 범위를 update한다.
In [11]:
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
@logging_time
def solution(a, show=False):
n, m = len(a), len(a[0])
cset = set([1,2,3,4,5])
def mark(x, y, dx, dy, fill):
i, j = x, y
x, y = x + dx, y + dy
while (0 <= x < n and 0 <= y < m):
if a[x][y] == 6: return
if a[x][y] not in cset:
a[x][y] += fill
x, y = x + dx, y + dy
def markAll(x, y, delta, kind, fill):
if kind == 1:
mark(x, y, *delta, fill)
elif kind == 2 or kind == 3:
mark(x, y, *delta[0], fill), mark(x, y, *delta[1], fill)
if kind == 4:
mark(x, y, *delta[0], fill), mark(x, y, *delta[1], fill), mark(x, y, *delta[2], fill)
if kind == 5:
mark(x, y, *delta[0], fill), mark(x, y, *delta[1], fill)
mark(x, y, *delta[2], fill), mark(x, y, *delta[3], fill)
def monitor(i, j, kind, fill):
for dij in directions[kind]:
markAll(i, j, dij, kind, fill)
yield dij
cctv = [(i, j) for i in range(n) for j in range(m) if a[i][j] and a[i][j] != 6]
ans = 1e20
snapshot = None
def dfs(idx):
nonlocal ans, snapshot
if idx == len(cctv):
loc = sum(1 for i in range(n) for j in range(m) if not a[i][j])
if loc < ans:
ans = loc
if show: snapshot = deepcopy(a)
return
i, j = cctv[idx]
for delta in monitor(i, j, kind=a[i][j], fill=-1): # minus 1
dfs(idx + 1)
markAll(i, j, delta, kind=a[i][j], fill=1) # plus 1
dfs(idx=0)
if show: plot(snapshot)
return ans
In [13]:
1
2
3
4
5
6
n, m = 5, 10
a = random2D(shape=(n, m), sampling=[0, 1, 2, 3, 4, 5, 6], weights=[0.7, 0.05, 0.05, 0.05 ,0.05, 0.05, 0.05])
plot(a)
cctv = [(i, j) for i in range(n) for j in range(m) if a[i][j] and a[i][j] != 6]
print("indices of cctv:",cctv)
solution(a, show=True, verbose=True)
1
2
3
4
5
6
7
8
9
10
11
12
13
[[6 0 0 3 3 0 0 6 4 6]
[0 1 0 0 0 0 0 0 3 0]
[0 0 3 0 0 6 0 0 0 0]
[0 0 0 0 1 1 6 0 6 0]
[0 3 3 0 0 2 0 0 6 0]]
indices of cctv: [(0, 3), (0, 4), (0, 8), (1, 1), (1, 8), (2, 2), (3, 4), (3, 5), (4, 1), (4, 2), (4, 5)]
[[ 6 -1 -1 3 3 -2 -2 6 4 6]
[-1 1 -3 -3 -3 -2 -2 -2 3 -1]
[-1 -2 3 -1 -1 6 0 0 -1 0]
[-1 -2 -3 -2 1 1 6 0 6 0]
[-1 3 3 -4 -3 2 -3 -3 6 0]]
WorkingTime[solution]: 21617.11788 ms
1
6
Time Complexity
Let’s define a notation of cctv as follows. \(|cctv| = k\)
- marking: $O(max(m, n))$
- cctv 마다 enumerate 수: $4$
따라서, $O(max(m, n) 4^k)$, 여기서 $k\le mn$
cctv 종류에 따라 enumerate 이 최대 4번까지 될 수 있고, 벽에의해 pruning(or backtracking) 되지 않는이상 오랜시간이 걸림.
Submitted Code
In [9]:
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
from sys import stdin
from copy import deepcopy
stdin = open('data/monitor.txt')
input = stdin.readline
n, m = list(map(int, input().split()))
a = [list(map(int, input().split())) for _ in range(n)]
up, down, left, right = (-1, 0), (1, 0), (0, -1), (0, 1)
directions = \
{1: [up, down, left, right],
2: [(up, down), (left, right)],
3: [(up, right), (right, down), (down, left), (left, up)],
4: [(left, up, right), (up, right, down), (right, down, left), (down, left, up)],
5: [(up, down, left, right)]}
def solution(a):
n, m = len(a), len(a[0])
cset = set([1,2,3,4,5])
def mark(x, y, dx, dy, fill):
i, j = x, y
x, y = x + dx, y + dy
while (0 <= x < n and 0 <= y < m):
if a[x][y] == 6: return
if a[x][y] not in cset:
a[x][y] += fill
x, y = x + dx, y + dy
def markAll(x, y, delta, kind, fill):
if kind == 1:
mark(x, y, *delta, fill)
elif kind == 2 or kind == 3:
mark(x, y, *delta[0], fill), mark(x, y, *delta[1], fill)
if kind == 4:
mark(x, y, *delta[0], fill), mark(x, y, *delta[1], fill), mark(x, y, *delta[2], fill)
if kind == 5:
mark(x, y, *delta[0], fill), mark(x, y, *delta[1], fill)
mark(x, y, *delta[2], fill), mark(x, y, *delta[3], fill)
def monitor(i, j, kind, fill):
for dij in directions[kind]:
markAll(i, j, dij, kind, fill)
yield dij
cctv = [(i, j) for i in range(n) for j in range(m) if a[i][j] and a[i][j] != 6]
ans = 1e20
def dfs(idx):
nonlocal ans
if idx == len(cctv):
ans = min(ans, sum(1 for i in range(n) for j in range(m) if not a[i][j]))
return
i, j = cctv[idx]
for delta in monitor(i, j, kind=a[i][j], fill=-1): # minus 1
dfs(idx + 1)
markAll(i, j, delta, kind=a[i][j], fill=1) # plus 1
dfs(idx=0)
return ans
print(solution(a))
1
2
15
Leave a comment