📄 문제
백준
난이도 : Gold 4
문제 제목 : 감시
✏️ 풀이 1
import sys
import copy
input = sys.stdin.readline
n, m = map(int, input().split())
cctv = []
matrix = []
for i in range(n):
row = list(map(int, input().split()))
matrix.append(row)
for j in range(m):
if row[j] in [1, 2, 3, 4, 5]:
cctv.append([row[j], i, j])
mode = [
[],
[[0], [1], [2], [3]],
[[0, 2], [1, 3]],
[[0, 1], [1, 2], [2, 3], [0, 3]],
[[0, 1, 2], [0, 1, 3], [1, 2, 3], [0, 2, 3]],
[[0, 1, 2, 3]],
]
dy = (-1, 0, 1, 0)
dx = (0, 1, 0, -1)
def upd(board, current_mode, y, x):
for i in current_mode:
ny = y
nx = x
while True:
ny += dy[i]
nx += dx[i]
if ny < 0 or nx < 0 or ny >= n or nx >= m:
break
if board[ny][nx] == 6:
break
elif board[ny][nx] == 0:
board[ny][nx] = 7
def dfs(depth, matrix):
global min_value
if depth == len(cctv):
count = 0
for i in range(n):
count += matrix[i].count(0)
min_value = min(min_value, count)
return
tmp = copy.deepcopy(matrix)
cctv_num, x, y = cctv[depth]
for i in mode[cctv_num]:
upd(tmp, i, x, y)
dfs(depth+1, tmp)
tmp = copy.deepcopy(matrix)
min_value = int(1e9)
dfs(0, matrix)
print(min_value)✅ 풀이 한줄 설명:
1. cctv의 종류와 위치를 배열에 저장한다.
2. cctv 배열 순서대로 깊이우선탐색(DFS)을 재귀적으로 수행한다. 이 때 모든 방향을 고려하여 탐색한다. (백트래킹)
3. cctv 배열 내 모든 cctv를 탐색하였으면 사각지대를 카운팅 해 최소값을 업데이트한다.
✅ 풀이 자세한 설명:
나올 수 있는 cctv들의 방향 조합들을 먼저 구해야 한다. 백트래킹으로도 풀 수 있지만, 이 문제의 경우 4진법을 이용할 수 있다. 이 포스팅에서는 4진법을 이용할 것이고, 자세한 방법은 아래를 참고바란다. 만약 백트래킹으로 푸는 것에 감이 안온다면 'BOJ. N과 M (3)' 문제를 먼저 풀어보자.
가능한 모든 방향 조합을 구한 후에는, 조합마다 감시되는 칸을 모두 마킹하여 사각지대를 카운팅하면 된다.
🍎 1. cctv의 종류와 위치를 배열에 저장한다.
가장 먼저 [{종류}, row, col] 요소를 가지는 cctv 배열을 구한다.
cctv = []
matrix = []
for i in range(n):
row = list(map(int, input().split()))
matrix.append(row)
for j in range(m):
if row[j] in [1, 2, 3, 4, 5]:
cctv.append([row[j], i, j])
# cctv 종류 별 가능한 감시 방향 리스트
mode = [
[],
[[0], [1], [2], [3]],
[[0, 2], [1, 3]],
[[0, 1], [1, 2], [2, 3], [0, 3]],
[[0, 1, 2], [0, 1, 3], [1, 2, 3], [0, 2, 3]],
[[0, 1, 2, 3]],
]🍎 2. cctv 배열 순서대로 깊이우선탐색(DFS)을 재귀적으로 수행한다.
재귀적 DFS 함수를 구현하기 전에, 먼저 cctv가 볼 수 있는 칸에 마킹하는 함수부터 구현한다.
dy = (-1, 0, 1, 0)
dx = (0, 1, 0, -1)
# cctv 모드(종류와 방향)에 따라 볼 수 있는 칸에 7을 마킹
def upd(board, current_mode, y, x):
for i in current_mode:
ny = y
nx = x
while True:
ny += dy[i]
nx += dx[i]
if ny < 0 or nx < 0 or ny >= n or nx >= m:
break
if board[ny][nx] == 6:
break
elif board[ny][nx] == 0:
board[ny][nx] = 7그리고 실제 cctv 배열 순서대로 깊이우선탐색을 하는 함수를 구현한다. 이 때, cctv별로 가능한 모든 방향을 고려해야 한다. (백트래킹) depth는 탐색한 cctv 수로, 0부터 시작한다.
def dfs(depth, matrix):
tmp = copy.deepcopy(matrix) # tmp = [list(row) for row in matrix] 도 가능
cctv_num, x, y = cctv[depth]
for i in mode[cctv_num]:
upd(tmp, i, x, y)
dfs(depth+1, tmp)
tmp = copy.deepcopy(matrix)위 dfs 함수는 재귀이지만 아직 base condition을 작성하지 않은 점을 유의한다.
🍎 cctv 배열 내 모든 cctv를 탐색하였으면 사각지대를 카운팅 해 최소값을 업데이트한다.
cctv 수만큼 탐색을 완료하였으면 이제 matrix에 필요한 모든 마킹이 완료되었을 것이다. 따라서 사각지대를 카운팅해 최소값을 업데이트한다.
즉, dfs 함수에 base condition을 작성해준다.
def dfs(depth, matrix):
global min_value
# base condition
if depth == len(cctv):
count = 0
for i in range(n):
count += matrix[i].count(0)
min_value = min(min_value, count)
return
tmp = copy.deepcopy(matrix)
cctv_num, x, y = cctv[depth]
for i in mode[cctv_num]:
upd(tmp, i, x, y)
dfs(depth+1, tmp)
tmp = copy.deepcopy(matrix)📦 GitHub
해당 문제, 풀이에 대한 GitHub Repository 링크는 다음과 같다.
GitHub - 백준(Gold) '15683. 감시'
GitHub - [13강] 시뮬레이션/연습문제 '15683. 감시'
이 문제는 구현 문제로 다양한 풀이가 나올 수 있다.
이 포스팅에서는 DFS(백트래킹)을 이용하여 구현하였지만, 진법을 이용한 소요 시간에서 더 효율적인 방법이 있다.
DFS를 이용한 방법이 좀 더 직관적이고 익숙한 느낌이 든다면, 진법을 이용한 풀이는 조금 더 신박한 풀이가 아닐까 싶다.
해당 방법이 궁금하다면 다음 링크를 참고바란다.
📄 BOJ.15683. 감시
풀이 포스팅 링크1
