Algorithm 문제
[백준] 15683 - 감시
노예2
2019. 7. 22. 21:10
https://www.acmicpc.net/problem/15683
15683번: 감시
스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감시할 수 있는 방법은 다음과 같다. 1번 CCTV는 한 쪽 방향만 감시할 수 있다. 2번과 3번은 두 방향을 감시할 수 있는데, 2번은 감시하는 방향이 서로 반대방향이어야 하고, 3번은 직각 방향이어야 한다. 4번은 세 방향, 5번은 네 방향을 감시할
www.acmicpc.net
백준 문제집 중 '삼성 sw 역량 테스트 기출문제'에 포함된 문제
해당 문제집은 거의 대부분 Brute-Force 문제인 듯.
재귀를 이용하여 모든 경우를 계산하였다.
pypy2로 컴파일 했음에도 제한시간이 아슬아슬했다. 더 좋은 방법이 있을 듯
<Python 코드>
|
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
|
import sys
import copy
lines = sys.stdin.readlines()
n, m = tuple(map(int, lines[0].split()))
room = [list(map(int, line.split())) for line in lines[1:]]
cctv_list = []
dy, dx = [-1, 0, 1, 0], [0, 1, 0, -1] # 상, 우, 하, 좌
def recu(depth, sight_list):
if depth == len(cctv_list):
tmp_room = copy.deepcopy(room)
for sight in sight_list:
d, y, x = sight
while(True):
if y < 0 or y >= n or x < 0 or x >= m or room[y][x] == 6:
break
tmp_room[y][x] = '#'
y, x = y + dy[d], x + dx[d]
re = 0
for l in tmp_room:
for p in l:
if p == 0:
re += 1
return re
cctv = cctv_list[depth]
case = []
if cctv[0] == 1:
for d in range(4):
case.append([(d, cctv[1], cctv[2])])
elif cctv[0] == 2:
for d in range(2):
case.append([(d, cctv[1], cctv[2]), (d+2, cctv[1], cctv[2])])
elif cctv[0] == 3:
for d in range(4):
case.append([(d, cctv[1], cctv[2]), ((d+1)%4, cctv[1], cctv[2])])
elif cctv[0] == 4:
for d in range(4):
case.append([(d, cctv[1], cctv[2]), ((d+1)%4, cctv[1], cctv[2]), ((d+2)%4, cctv[1], cctv[2])])
elif cctv[0] == 5:
case.append([(0, cctv[1], cctv[2]), (1, cctv[1], cctv[2]), (2, cctv[1], cctv[2]), (3, cctv[1], cctv[2])])
re = 100
for c in case:
re = min(re, recu(depth+1, sight_list + c))
return re
for i in range(n):
for j in range(m):
if 1<=room[i][j]<=5:
cctv_list.append((room[i][j], i, j))
sys.stdout.write(str(recu(0, [])))
|
cs |