감시
CCTV가 감시할 수 있는 구역을 찾아내는 구현 문제이다. CCTV의 종류에 따라 감시할 수 있는 방향이 다르고, 벽 넘어는 감시할 수 없다.
1~5번까지의 CCTV에 대해서 각각 함수를 짜 주었다. 너무 무식하게 복사 붙여넣기로 함수를 만들어서 코드가 굉장히 길어졌다…
- 1번 CCTV가 감시할 수 있는 영역의 경우의 수는 위아래, 좌우 이렇게 4가지가 있다.
- 2번 CCTV의 경우 2가지
- 3번 CCTV의 경우 4가지
- 4번 CCTV의 경우 4가지
- 5번 CCTV의 경우 1가지
이렇게 경우의 수를 함수의 인자로 받아서 그 경우에 대해 감시할 수 있는 영역의 정보를 return 했다.
def one(direction, a, b):
1번 CCTV에 대한 함수인데, 감시할 수 있는 경우의 수 4가기중 한 가지를 선택하기 위한 direction과 CCTV의 위치 정보를 인자로 받았다. direction의 값은 0,1,2,3 중 하나이다.
위의 함수는 몇개의 칸을 감시할 수 있는지와, 각각의 감시 가능한 칸의 좌표를 return한다.
각 CCTV들이 감시할 수 있는 영역의 경우의 수를 DFS로 전부 탐색하며 사각지대의 최소값을 찾아냈다.
- ❌코드가 굉장히 길다… 오늘의 포스팅을 해야하기에 일단 이렇게 업로드 하지만, 추후에 코드 길이를 줄여서 다시 한 번 포스팅 하도록 해야겠다.❌
CODE
import sys
read = sys.stdin.readline
n, m = map(int, read().split())
MAP = list(list(map(int, read().split())) for _ in range(n))
CCTV = list()
n_cctv = 0
WALL = list()
count = n*m
for i in range(n):
for j in range(m):
if MAP[i][j] == 6:
WALL.append((i, j))
count -= 1
elif MAP[i][j] > 0:
CCTV.append((MAP[i][j], i, j))
n_cctv += 1
count -= 1
def one(direction, a, b):
point = [0]
if direction == 0:
for i in range(n):
ai = a+i
if ai < n:
if MAP[ai][b] == 6:
return point
elif MAP[ai][b] == 0:
point[0] += 1
point.append([ai, b])
else:
continue
else:
break
if direction == 1:
for i in range(n):
ai = a-i
if ai >= 0:
if MAP[ai][b] == 6:
return point
elif MAP[ai][b] == 0:
point[0] += 1
point.append([ai, b])
else:
continue
else:
break
if direction == 2:
for i in range(m):
bi = b-i
if bi >= 0:
if MAP[a][bi] == 6:
return point
elif MAP[a][bi] == 0:
point[0] += 1
point.append([a, bi])
else:
continue
else:
break
if direction == 3:
for i in range(m):
bi = b+i
if bi < m:
if MAP[a][bi] == 6:
return point
elif MAP[a][bi] == 0:
point[0] += 1
point.append([a, bi])
else:
continue
else:
break
return point
def two(direction, a, b):
point = [0]
if direction == 0:
for i in range(n):
ai = a-i
if ai >= 0:
if MAP[ai][b] == 6:
break
elif MAP[ai][b] == 0:
point[0] += 1
point.append([ai, b])
else:
continue
else:
break
for i in range(n):
ai = a+i
if ai < n:
if MAP[ai][b] == 6:
break
elif MAP[ai][b] == 0:
point[0] += 1
point.append([ai, b])
else:
continue
else:
break
if direction == 1:
for i in range(m):
bi = b-i
if bi >= 0:
if MAP[a][bi] == 6:
break
elif MAP[a][bi] == 0:
point[0] += 1
point.append([a, bi])
else:
continue
else:
break
for i in range(m):
bi = b+i
if bi < m:
if MAP[a][bi] == 6:
break
elif MAP[a][bi] == 0:
point[0] += 1
point.append([a, bi])
else:
continue
else:
break
return point
def three(direction, a, b):
point = [0]
if direction == 0:
for i in range(n):
ai = a-i
if ai >= 0:
if MAP[ai][b] == 6:
break
elif MAP[ai][b] == 0:
point[0] += 1
point.append([ai, b])
else:
continue
else:
break
for i in range(m):
bi = b+i
if bi < m:
if MAP[a][bi] == 6:
break
elif MAP[a][bi] == 0:
point[0] += 1
point.append([a, bi])
else:
continue
else:
break
if direction == 1:
for i in range(n):
ai = a+i
if ai < n:
if MAP[ai][b] == 6:
break
elif MAP[ai][b] == 0:
point[0] += 1
point.append([ai, b])
else:
continue
else:
break
for i in range(m):
bi = b+i
if bi < m:
if MAP[a][bi] == 6:
break
elif MAP[a][bi] == 0:
point[0] += 1
point.append([a, bi])
else:
continue
else:
break
if direction == 2:
for i in range(n):
ai = a+i
if ai < n:
if MAP[ai][b] == 6:
break
elif MAP[ai][b] == 0:
point[0] += 1
point.append([ai, b])
else:
continue
else:
break
for i in range(m):
bi = b-i
if bi >= 0:
if MAP[a][bi] == 6:
break
elif MAP[a][bi] == 0:
point[0] += 1
point.append([a, bi])
else:
continue
else:
break
if direction == 3:
for i in range(n):
ai = a-i
if ai >= 0:
if MAP[ai][b] == 6:
break
elif MAP[ai][b] == 0:
point[0] += 1
point.append([ai, b])
else:
continue
else:
break
for i in range(m):
bi = b-i
if bi >= 0:
if MAP[a][bi] == 6:
break
elif MAP[a][bi] == 0:
point[0] += 1
point.append([a, bi])
else:
continue
else:
break
return point
def four(direction, a, b):
point = [0]
if direction == 0:
for i in range(m):
bi = b+i
if bi < m:
if MAP[a][bi] == 6:
break
elif MAP[a][bi] == 0:
point[0] += 1
point.append([a, bi])
else:
continue
else:
break
for i in range(n):
ai = a+i
if ai < n:
if MAP[ai][b] == 6:
break
elif MAP[ai][b] == 0:
point[0] += 1
point.append([ai, b])
else:
continue
else:
break
for i in range(m):
bi = b-i
if bi >= 0:
if MAP[a][bi] == 6:
break
elif MAP[a][bi] == 0:
point[0] += 1
point.append([a, bi])
else:
continue
else:
break
if direction == 1:
for i in range(n):
ai = a-i
if ai >= 0:
if MAP[ai][b] == 6:
break
elif MAP[ai][b] == 0:
point[0] += 1
point.append([ai, b])
else:
continue
else:
break
for i in range(n):
ai = a+i
if ai < n:
if MAP[ai][b] == 6:
break
elif MAP[ai][b] == 0:
point[0] += 1
point.append([ai, b])
else:
continue
else:
break
for i in range(m):
bi = b-i
if bi >= 0:
if MAP[a][bi] == 6:
break
elif MAP[a][bi] == 0:
point[0] += 1
point.append([a, bi])
else:
continue
else:
break
if direction == 2:
for i in range(n):
ai = a-i
if ai >= 0:
if MAP[ai][b] == 6:
break
elif MAP[ai][b] == 0:
point[0] += 1
point.append([ai, b])
else:
continue
else:
break
for i in range(m):
bi = b+i
if bi < m:
if MAP[a][bi] == 6:
break
elif MAP[a][bi] == 0:
point[0] += 1
point.append([a, bi])
else:
continue
else:
break
for i in range(m):
bi = b-i
if bi >= 0:
if MAP[a][bi] == 6:
break
elif MAP[a][bi] == 0:
point[0] += 1
point.append([a, bi])
else:
continue
else:
break
if direction == 3:
for i in range(n):
ai = a-i
if ai >= 0:
if MAP[ai][b] == 6:
break
elif MAP[ai][b] == 0:
point[0] += 1
point.append([ai, b])
else:
continue
else:
break
for i in range(m):
bi = b+i
if bi < m:
if MAP[a][bi] == 6:
break
elif MAP[a][bi] == 0:
point[0] += 1
point.append([a, bi])
else:
continue
else:
break
for i in range(n):
ai = a+i
if ai < n:
if MAP[ai][b] == 6:
break
elif MAP[ai][b] == 0:
point[0] += 1
point.append([ai, b])
else:
continue
else:
break
return point
def five(direction, a, b):
point = [0]
if direction == 0:
for i in range(n):
ai = a-i
if ai >= 0:
if MAP[ai][b] == 6:
break
elif MAP[ai][b] == 0:
point[0] += 1
point.append([ai, b])
else:
continue
else:
break
for i in range(m):
bi = b+i
if bi < m:
if MAP[a][bi] == 6:
break
elif MAP[a][bi] == 0:
point[0] += 1
point.append([a, bi])
else:
continue
else:
break
for i in range(n):
ai = a+i
if ai < n:
if MAP[ai][b] == 6:
break
elif MAP[ai][b] == 0:
point[0] += 1
point.append([ai, b])
else:
continue
else:
break
for i in range(m):
bi = b-i
if bi >= 0:
if MAP[a][bi] == 6:
break
elif MAP[a][bi] == 0:
point[0] += 1
point.append([a, bi])
else:
continue
else:
break
return point
def DFS(index):
global count, answer
if index == n_cctv:
answer = min(answer, count)
return
t, a, b = CCTV[index]
if t == 1:
for i in range(4):
point = one(i, a, b)
count -= point[0]
for x, y in point[1:]:
MAP[x][y] = -1
DFS(index+1)
count += point[0]
for x, y in point[1:]:
MAP[x][y] = 0
elif t == 2:
for i in range(2):
point = two(i, a, b)
count -= point[0]
for x, y in point[1:]:
MAP[x][y] = -1
DFS(index+1)
count += point[0]
for x, y in point[1:]:
MAP[x][y] = 0
if t == 3:
for i in range(4):
point = three(i, a, b)
count -= point[0]
for x, y in point[1:]:
MAP[x][y] = -1
DFS(index+1)
count += point[0]
for x, y in point[1:]:
MAP[x][y] = 0
if t == 4:
for i in range(4):
point = four(i, a, b)
count -= point[0]
for x, y in point[1:]:
MAP[x][y] = -1
DFS(index+1)
count += point[0]
for x, y in point[1:]:
MAP[x][y] = 0
if t == 5:
for i in range(1):
point = five(i, a, b)
count -= point[0]
for x, y in point[1:]:
MAP[x][y] = -1
DFS(index+1)
count += point[0]
for x, y in point[1:]:
MAP[x][y] = 0
answer = sys.maxsize
DFS(0)
print(answer)
틀린 부분이 있을 수 있습니다. 피드백 주시면 고치도록 하겠습니다!
감사합니다.👍
[꼭 다시 풀어보기]