백준 문제/BFS,DFS
[필수]백준 : 감시_15683
goldpig
2024. 1. 31. 14:55
728x90
https://www.acmicpc.net/problem/15683
15683번: 감시
스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감
www.acmicpc.net
핵심 아이디어
- DFS + 구현
문제 해결 방법
- mode라는 리스트로 CCTV의 종류(1, 2, 3, 4, 5)에 따라 회전했을 때 바라보는 방향을 넣어줌
- 사무실의 정보를 입력받을 때, cctv의 종료 및 위치(i,j)를 cctv 리스트에 append
- DFS를 돌려서 해당 cctv의 종류의 각도로 감시를 실행한 후, cctv 갯수만큼 CCTV로 감시를 다 했을 때 사각지대의 최솟값을 갱신
- CCTV의 방향에 따라 범위를 벗어나지 않거나 벽을 만나지 않는 이상 계속 탐색하며 감시한 곳은 -1로표시
구현 코드
'''
DFS와 브루트포스 알고리즘. CCTV를 회전할 수 있기 때문에
이 회전 가능한 경우의 수를 모두 따져주어 사각지대 계산
'''
import copy # 원래 값이 담겨있는 배열을 깊은 복사하기 위함
n, m = map(int, input().split())
cctv = [] # cctv종류, x좌표, y좌표
graph = []
# 각 CCTV의 종류와 위치를 저장하는 리스트
mode = [
[],
[[0],[1],[2],[3]], # 0부터 동 남 서 북, 1번, 한 쪽방향 감시
[[0,2],[1,3]], # 2번, 양 쪽 방향 감시
[[0,1],[1,2],[2,3],[0,3]], # 3번, 직각 방향 감시
[[0,1,2],[0,1,3],[1,2,3],[2,3,0]], # 4번, 세 방향 감시
[[0,1,2,3]], # 5번, 네 방향 감시
]
for i in range(n):
graph.append(list(map(int, input().split())))
for j in range(m):
if graph[i][j] in [1,2,3,4,5]:
cctv.append([graph[i][j], i, j]) # CCTV의 종류, x좌표, y좌표
# 북 동 남 서
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
# CCTV의 방향에 따라서 범위를 넘어가지 않거나, 벽을 만나지 않는 이상
# 계속 감시를 하며 감시 되는 위치는 -1로 표시
def check(graph, mode, x,y): # 감시, mode = 1 ~ 5
for i in mode: #CCTV의 방향에 따라서
# CCTV의 현재 위치를 nx와 ny에 할당합니다. x와 y는 CCTV의 초기 위치
nx, ny = x,y
#무한 루프를 사용하여 각 방향으로 계속 이동하면서 감시 영역을 탐색합니다.
#이 루프는 벽을 만나거나 맵의 경계를 벗어날 때까지 계속
while True: # 범위 벗어나지 않고 벽을 만나지 않는 이상 계속 감시
nx += dx[i]
ny += dy[i]
# 범위를 벗어나면 중단
if nx < 0 or nx >= n or ny < 0 or ny >=m:
break # 반복문 탈출
# 벽이면 중단
if graph[nx][ny] == 6:
break
elif graph[nx][ny] == 0: # 감시 가능
graph[nx][ny] = -1 # 감시 가능 표시
# dfs 알고리즘 수행
#DFS를 돌려서 해당 cctv의 종류의 각도로 감시를 실행한 후,
#cctv 갯수만큼 CCTV로 감시를 다 했을 때
#사각지대의 최솟값을 갱신한다.
min_value = int(1e9)
def dfs(depth, graph): # 탐색
global min_value # 최솟값
if depth == len(cctv): # 탐색완료
count = 0
for i in range(n): # 사각지대 찾기
# 각 행마다 0 카운트
count += graph[i].count(0)
# 최솟값 업데이트
min_value = min(min_value,count)
return
else:
temp = copy.deepcopy(graph) # 맵 복제
cctv_num,x,y = cctv[depth] # 탐색할 cctv
for i in mode[cctv_num]: # cctv방향에 따라서
check(temp, i, x,y)
dfs(depth+1, temp) # 재귀 호출
# 재귀 호출이 끝나면 맵 다시 초기화, 다음 탐색을 위해
temp = copy.deepcopy(graph)
dfs(0, graph)
print(min_value)
728x90