[DFS/BFS/완전탐색] ★ 15683번 - 감시(DFS, 완전탐색)

[백준] 15683번 - 감시

풀이 시간: 2시간 이내

 

1) 문제 해결 아이디어

사각 지대의 최소 크기를 출력하는 문제다. 처음에는 아무생각없이 BFS로 풀어도 되나하는 문제였지만 cctv들의 방향을 설정하는 모든 경우의 수를 고려하여 풀어야 하는 완전탐색 문제로 DFS를 이용하여 풀어야했다. 지금까지 풀었던 문제는 되게 단순하고 정형화된 문제였기때문에 새로운 방식으로 풀려고 아이디어를 떠올리는데 시간이 많이 걸렸다. 추후 꼭 복습이 필요한 문제!!

 

<CCTV 번호별 경우의 수>

나는 북, 동, 남, 서 방향을 차례대로 0, 1, 2, 3 으로 설정하였다.

CCTV 번호에 따른 방법(방향 경우의 수)수는 다음과 같다.

 

첫번째 오류. 틀렸습니다

nx, ny를 x, y로 초기화해야 하는데, dx를 1번 더해준 값으로 초기화해서 문제가 생겼다.

 

<동작 과정>

1. 입력받은 사무실 정보(graph)에서 CCTV의 번호와 좌표를 리스트(cctv)에 저장, cctv 개수 세기

2. dfs 호출 

매개변수로 입력받은 사무실 정보(graph)와 깊이(0)을 넘겨줌

3. 사각 지대 최솟값(min_blind) 출력

 

<dfs 동작과정>

1. 매개변수로 넘겨받은 사무실 정보(graph)를 temp에 깊은 복사

2. 깊이가 CCTV 개수(k)가 되었다면 모든 CCTV 방법이 설정되었으므로 사각지대 개수 세기, 최솟값 업데이트 후 종료

3. depth번째 CCTV의 좌표와 cctv 번호를 변수에 저장함

4. cctv 번호에 해당하는 모든 방법들(way)에 대해 감시 진행하기

4-1. 해당 방법(way)의 cctv 방향(d)에 따라 감시 진행(이동하기)

4-1-1. 이동해야할 칸(nx, ny)를 현재 cctv 좌표(x,y)로 초기화 하기

4-1-2. 해당 방향(d)로 계속 직진하기

4-1-2-1. 범위 내이고 빈칸이면 temp에 # 으로 체크하기

4-1-2-2. 범위 내이고 벽이면 break(다음 방향 검사하기)

4-1-2-3. 범위 밖이면 break(다음 방향 검사하기) 

4-2. dfs(temp, depth + 1) 호출하기

4-1번에서 진행되어 바뀐 결과(temp)와 깊이(depth)를 1증가시켜 매개변수로 넘김

4-3. dfs 전의 사무실 정보(graph)로 temp 원상복귀

 

2) 소스코드

from copy import deepcopy
import sys
input = sys.stdin.readline

# DFS
def dfs(graph, depth):
  global k, min_blind  
  temp = deepcopy(graph)  # 깊은 복사
  # 모든 CCTV 방향이 설정되었다면
  if depth == k:
    blind = 0  # 사각지대 개수
    # 사각지대 개수 세기
    for i in range(n):
      blind += temp[i].count(0)
    min_blind = min(min_blind, blind)  # 최솟값 업데이트
    return

  x, y, cctv_num = cctv[depth]  # 좌표, cctv 번호
  # 해당 cctv 번호의 방법들에 대해 반복
  for way in dir[cctv_num]:
    # 1. 해당 cctv 번호의 방법에 대한 방향으로 이동
    for d in way:
      nx, ny = x, y  # 이동해야할 좌표
      while True:
        # 해당 방향으로 계속 직진
        nx += dx[d]
        ny += dy[d]
        # 범위 내이고
        if 0 <= nx < n and 0 <= ny < m:
          # 빈칸이면 체크하기
          if temp[nx][ny] == 0:  temp[nx][ny] = '#'
          # 벽이면 탈출
          elif temp[nx][ny] == 6:  break
        # 범위 밖이면 탈출
        else:  break
    # 2. dfs 호출
    dfs(temp, depth + 1)
    # 3. dfs 전으로 원상복귀
    temp = deepcopy(graph)  

# 북, 동, 남, 서
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
# CCTV 방향(1~5)
dir = [
  [],
  [[0], [1], [2], [3]],
  [[0, 2], [1, 3]],
  [[0, 1], [1, 2], [2, 3], [3, 0]],
  [[0, 1, 2], [1, 2, 3], [2, 3, 0], [3, 0, 1]],
  [[0, 1, 2, 3]],
]
    
n, m = map(int, input().split())  # 세로, 가로
# n * m (0: 빈칸, 1~5: CCTV, 6:벽)
graph = [list(map(int, input().split())) for _ in range(n)]
min_blind = 1e9  # 사각지대 최소 크기
cctv = []  # cctv 좌표, 번호 목록
k = 0      # cctv 개수
# CCTV 번호, 좌표 찾기
for i in range(n):
  for j in range(m):
    # CCTV면
    if 1 <= graph[i][j] <= 5:
      cctv.append((i, j, graph[i][j]))  # 좌표, cctv번호
      k += 1

dfs(graph, 0)
print(min_blind)

[참고] https://developer-ellen.tistory.com/53

BOJ - 감시 15683번 (python)