[백준15683&파이썬] 여러경우의 4방향 탐색 및 회전 가지치기와 완전탐색

# 문제

백준 15683 감시 파이썬 풀이

15683번: 감시

# 코드

import sys

def print2D(arr) :
  for i in arr :
    print(i)

DIRS = [
  (-1,0),(0,1),(1,0),(0,-1)
  ]

CCTVS_DIR = [
  [-1],
  [1], # 1
  [1,3], # 2
  [0,1], # 3
  [0,1,3], # 4
  [0,1,2,3], # 5
  ]

N,M = map(int,sys.stdin.readline().split())
board = list()

cctvs = list()
zero_cnt = 0
for row in range(N) :
  line = list(map(int,sys.stdin.readline().split()))
  board.append(line)

  for col,data in enumerate(line) :
    if 1<= data <= 5 :
      cctvs.append((row,col,data)) # row , col , CCTV종류
    if data == 0 :
      zero_cnt +=1

stk = list()
result = 0
def dfs(depth) :
  global CCTVS_DIR,cctvs,DIRS,stk,result
  if depth == len(cctvs) :
    # print(stk)
    visit = [ [False] * M for _ in range(N)]
    cnt = 0
    for idx,cctv_dirs in enumerate(stk) :
      start_row,start_col,data = cctvs[idx]

      for dir in cctv_dirs :
        pr, pc = DIRS[dir]
        cur_row = start_row
        cur_col = start_col

        while True :
          cur_row = cur_row + pr
          cur_col = cur_col + pc
          if 0<= cur_row < N and 0<= cur_col < M and board[cur_row][cur_col] != 6 :
            if not visit[cur_row][cur_col] and board[cur_row][cur_col] == 0 :
              cnt +=1
              visit[cur_row][cur_col] = True # 방문처리
          else :
            break

    result = max(cnt,result)
    return

  row,col,ctype = cctvs[depth]
  record_dirs = CCTVS_DIR[ctype]
  if ctype == 5 :
    stk.append(record_dirs)
    dfs(depth+1)
    stk.pop()

  elif ctype == 2 :
    for i in range(2) :
      temp = list()
      for record_dir in record_dirs :
        nd = (record_dir + i) % 4
        temp.append(nd)
      stk.append(temp)
      dfs(depth+1)
      stk.pop()

  else :
    for i in range(4) :
      temp = list()
      for record_dir in record_dirs :
        nd = (record_dir + i) % 4
        temp.append(nd)
      stk.append(temp)
      dfs(depth+1)
      stk.pop()

dfs(0)
print(zero_cnt-result)

# 풀이

• 문제 풀이를 위한 핵심 전략은 존재하는 모든 CCTV를 90도방향으로 회전시키는 모든 경우의 수를 구해내는 것이다.
• 다만 5번 CCTV는 90도 회전을 해봤자 똑같은 곧이 탐색되기 때문에 회전 시키지 않는다.
• 다만 2번 CCTV는 현재 위치와 90도 위치로 총 두번만 돌려보면 해당 CCTV로 탐색되는 모든 경우의 수를 구할 수 있다.
• 1,3,4번의 CCTV만 4방향으로 90도로 돌려볼 수 있다.
• 5번과 2번 CCTV와 같은 특수한 경우를 따로 생각하지 않는다면 연산해야 하는 횟수가 크게 늘어나게 될 것이다. 이를 감안해서 모든 경우의 수를 구할 수 있도록 하는 dfs코드를 작성한다.
• CCTV의 회전을 용이하게 하기 위해 CCTVS_DIR은 DIRS의 인덱스를 가지고 있도록 한다. 이렇게 함으로써 쉽게 방향을 회전시킬 수 있다.

for record_dir in record_dirs :
    nd = (record_dir + i) % 4

• stk에는 CCTV의 탐색 방향이 담겨 있다. 모든 depth의 끝에 도달한다면, 이제는 살펴봐야하는 방향 정보를 토대로 "#"이 들어가야할 위치를 계산한다.

while True :
    cur_row = cur_row + pr
    cur_col = cur_col + pc
        if 0<= cur_row < N and 0<= cur_col < M and board[cur_row][cur_col] != 6 :
            if not visit[cur_row][cur_col] and board[cur_row][cur_col] == 0 :
                cnt +=1
                visit[cur_row][cur_col] = True # 방문처리
            else :
                break

• 위 코드를 통해서 CCTV가 볼 수 있는 곳을 계산한다.

if not visit[cur_row][cur_col] and board[cur_row][cur_col] == 0 :

• 특히 방문처리를 통한 이 조건절 하나만으로 CCTV가 있는 위치면 그냥 뛰어넘게 하는 것이 가능하다.
• 최종 정답은 사각지대가 최소가 되는 경우를 구해야 하기 때문에, CCTV로 가장 많은 "#"을 찍는 경우를 result에 저장한 후,
• 모든 0을 카운트했던 값에서 result를 빼주어 최종 답을 계산한다.