문제
https://www.acmicpc.net/problem/15683
주요 아이디어
생각보다 구현이 까다로운 문제였다.
위 다섯 종류의 90도 회전이 가능한 감시 카메라가 맵에 배치되어 있으며, 맵 전체에서 사각지대 영역의 최소 넓이를 측정하는 문제이다.
또한 CCTV는 서로를 통과할 수 없다는 조건이 걸려있다.
- CCTV는 8개 이하이므로 완전탐색 (=브루트 포스) 으로 문제를 해결한다
- CCTV의 회전 방향을 따로 rotation 배열에 저장해둔다
- 맵에 있는 모든 CCTV를 회전시켜보고, 그 때마다 면적을 체크해서 최소 면적으로 갱신한다
코드 구현 (Python 3)
더보기
"""
사각지대를 최소화하기
브루트포스니까 모든 경우의 수 전부 비교
1. 감시 당하는 부분 #으로 표시
2. CCTV 좌표 저장해두고, 하나씩 회전해보기
3. 사각지대 최소값 저장
0 -> 3 (시계방향 회전)
"""
import sys
import copy
# CCTV 방향
rotation = [
[],
[[0], [1], [2], [3]],
[[0, 2], [1, 3]],
[[0, 1], [1, 2], [2, 3], [0, 3]],
[[0, 1, 2], [0, 1, 3], [1, 2, 3], [0, 2, 3]],
[[0,1,2,3]]
]
# dx, dy 시계방향 (북 ~ 서)
direction = [[-1, 0], [0, 1], [1, 0], [0, -1]]
def fill(graph, y, x, rotate):
n = len(graph); m = len(graph[0])
for i in rotate:
ny = y; nx = x
while True:
ny += direction[i][1]
nx += direction[i][0]
# 벽이면 중단
if nx < 0 or ny < 0 or ny >= n or nx >= m or graph[ny][nx] == '6':
break
elif graph[ny][nx] == '0':
graph[ny][nx] = '#'
def dfs(depth, graph, cctv):
global min_area
# 탐색 완료
if depth == len(cctv):
min_area = min(check_area(graph), min_area)
return
graph_copy = copy.deepcopy(graph)
y, x, cctv_num = cctv[depth]
for r in rotation[int(cctv_num)]:
fill(graph_copy, y, x, r)
dfs(depth+1, graph_copy, cctv)
# 보드 초기화
graph_copy = copy.deepcopy(graph)
# 전체 면적 체크
def check_area(graph):
cnt = 0
for i in range(n):
for j in range(m):
if graph[i][j] == '0':
cnt += 1
return cnt
def solution(n, m):
graph = []
cctv = [] # (y, x, num)
for _ in range(n):
graph.append(sys.stdin.readline().rstrip().split())
# 초기 그래프 표시 & CCTV 위치 저장
for i in range(n):
for j in range(m):
if graph[i][j] != '0' and graph[i][j] != '6':
cctv.append([i, j, graph[i][j]])
# dfs 진행
dfs(0, graph, cctv)
return
n, m = map(int, input().split())
min_area = n*m
solution(n, m)
print(min_area)
제출 결과
'알고리즘 > BOJ' 카테고리의 다른 글
[BOJ] 2630. 색종이 만들기 (0) | 2024.06.25 |
---|---|
[BOJ] 15686. 치킨 배달 (0) | 2024.06.25 |
[BOJ] 13414. 수강신청 (0) | 2024.05.21 |
[BOJ] 1806. 부분합 (0) | 2024.05.21 |
[BOJ] 9466. 텀 프로젝트 (0) | 2024.04.24 |