728x90
15683번: 감시
스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감
www.acmicpc.net
분석
- cctv 방향 배열 생성
- dfs를 통해 격자 탐색
- 격자를 복사한 뒤, cctv별 방향으로 연속 탐색 후 dfs 수행
- 그래프 복귀 (방문 처리 초기화)
dfs 그래프 초기화
경로탐색(DFS)
[1260번] DFS, BFS 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호
karla.tistory.com
한방향 연속 탐색
[6087] 레이저 통신 (BFS)
6087번: 레이저 통신 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저
karla.tistory.com
풀이
"""
↑ ↑ ↑ ↑ ↑
1 2 ←3 ←4⟶ ←5⟶
↓ ↓
첫째 줄에 사무실의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 8)
둘째 줄부터 N개의 줄에는 사무실 각 칸의 정보가 주어진다. 0은 빈 칸, 6은 벽, 1~5는 CCTV를 나타내고, 문제에서 설명한 CCTV의 종류이다.
CCTV의 최대 개수는 8개를 넘지 않는다.
첫째 줄에 사각 지대의 최소 크기를 출력한다.
4 6
0 0 0 0 0 0
0 0 0 0 0 0
0 0 1 0 6 0
0 0 0 0 0 0
"""
import sys
import copy
input=sys.stdin.readline
sys.setrecursionlimit(10**9)
n,m=map(int,input().split())
board=[] # 사무실
cctv=[]
for i in range(n):
data = list(map(int, input().split()))
board.append(data)
for j in range(m):
if data[j] in [1, 2, 3, 4, 5]:
cctv.append([data[j], i, j])
min_value = sys.maxsize # 사각지대 최소크기
# 네방향
dr=[0,1,0,-1]
dc=[1,0,-1,0]
# cctv 방향
mode = [
[],
[[0], [1], [2], [3]], # 단방향
[[0, 2], [1, 3]], # 반대 두방향
[[0, 1], [1, 2], [2, 3], [0, 3]], # 90도 두방향
[[0, 1, 2], [0, 1, 3], [1, 2, 3], [0, 2, 3]], # 90도 세방향
[[0, 1, 2, 3]],] # 네방향
def dfs(idx, board):
global min_value
# 전체 cctv 탐색완료
if idx == len(cctv):
count = 0
# 사각지대 카운트
for i in range(n):
count += board[i].count(0)
min_value = min(min_value, count)
return
board_cp = copy.deepcopy(board) # 사무실 복사
cctv_num, x, y = cctv[idx]
# cctv의 방향에 따라서 탐색
for i in mode[cctv_num]:
for j in i:
nx=x
ny=y
# 한 방향 계속 탐색
while True:
nx+=dr[j]
ny+=dc[j]
if nx < 0 or ny < 0 or nx >= n or ny >= m: # 범위를 넘어가면 중단
break
if board_cp[nx][ny] == 6: # 벽이면 중단
break
elif board_cp[nx][ny] == 0: # 감시가능
board_cp[nx][ny] = '#'
dfs(idx+1, board_cp)
board_cp = copy.deepcopy(board) # 보드 초기화
dfs(0, board)
print(min_value)
728x90