방구석프로의 이야기

https://www.acmicpc.net/problem/15683

문제 해결을 위한 과정

이 문제의 경우 백트래킹을 이용해서 풀 수 있었습니다. 가장 중요한 건 각 cctv별로 이동할 수 있는 부분을 다음과 같이

direction = [
  [[0], [1], [2], [3]],
  [[0, 2], [1, 3]],
  [[0, 1], [1, 2], [2, 3], [3, 0]],
  [[0, 1, 3], [0, 1, 2], [1, 2, 3], [2, 3, 0]],
  [[0, 1, 2, 3]]
]

리스트 형태로 표현할 수 있어야 한다는 것 입니다. 1번(0번 인덱스) 카메라는 한 번에 한 방향만을, 2번(1번 인덱스) 카메라는 위아래 혹은 좌우를, 3번(2번 인덱스) 카메라는 90도만큼 두 개의 방향을, 4번 (3번 인덱스) 카메라는 한 번에 세 방향을, 5번(4번 인덱스) 카메라는 상하좌우 모두를 감시할 수 있습니다. 이 것을 코드로 표현하면 위의 소스코드와 같습니다.

이때 백트래킹(dfs)으로 모든 경우를 조회하면 해결할 수 있었습니다. 단 이때 원본 배열(graph)에 현재 감시 상황을 덮어씌우면 안 되므로 copy.deepcopy를 이용해 새로운 복사 배열을 생성하여 넘겨주어야 합니다.

소스코드

import copy

n, m = map(int, input().split())
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
ans = int(1e9)
direction = [
  [[0], [1], [2], [3]],
  [[0, 2], [1, 3]],
  [[0, 1], [1, 2], [2, 3], [3, 0]],
  [[0, 1, 3], [0, 1, 2], [1, 2, 3], [2, 3, 0]],
  [[0, 1, 2, 3]]
]

camera = []
graph = []

for _ in range(n):
  graph.append(list(map(int, input().split())))
for i in range(n):
  for j in range(m):
    if 1 <= graph[i][j] <= 5:
      camera.append((i, j, graph[i][j]))

def dfs(depth, tempGraph):
  global ans
  if depth == len(camera):
    cnt = 0
    for i in range(n):
      for j in range(m):
        if tempGraph[i][j] == 0:
          cnt += 1
    ans = min(ans, cnt)
    return 

  temp = copy.deepcopy(tempGraph)
  x, y, cctv = camera[depth]
  for i in range(len(direction[cctv-1])):
    for j in range(len(direction[cctv-1][i])):
      tx, ty = x, y
      while True:
        nx = tx + dx[direction[cctv-1][i][j]]
        ny = ty + dy[direction[cctv-1][i][j]]
        if nx < 0 or ny < 0 or nx >= n or ny >= m:
          break
        if temp[nx][ny] == 6:
          break
        if temp[nx][ny] == 0:
          temp[nx][ny] = cctv
        tx, ty = nx, ny
    dfs(depth + 1, temp)
    temp = copy.deepcopy(tempGraph)
    tx, ty = x, y
dfs(0, graph)
print(ans)