728x90
문제 보기
이 문제는 브루트 포스 문제이다.
2차원 배열에 존재하는 CCTV의 가능한 모든 방향을 다 고려한 후 사각지대의 최소 크기를 출력하면 된다.
1번 -> 상, 하, 좌, 우
2번 -> (상, 하), (좌, 우)
3번 -> (상, 우), (우, 하), (하, 좌), (좌, 상)
4번 -> (좌, 상, 우), (상, 우, 하), (우, 하, 좌), (하, 좌, 상)
5번 -> (상, 하, 좌, 우)
5가지 CCTV가 움직일 수 있는 방향은 위와 같으며 코드 상에서 반복적으로 나오는 부분이 많아서 코드의 길이가 길다.
코드
import sys
import copy
def dfs(idx):
global min_area, arr
if idx == len(position):
temp = 0
for i in range(N):
for j in range(M):
if arr[i][j] == 0:
temp += 1
min_area = min(min_area, temp)
else:
value, row, col = position[idx]
temp = copy.deepcopy(arr)
if value == 1:
# 상
for i in range(row - 1, -1, -1):
if arr[i][col] == 0:
arr[i][col] = '#'
elif arr[i][col] == 6:
break
dfs(idx + 1)
# 하
arr = copy.deepcopy(temp)
for i in range(row + 1, N):
if arr[i][col] == 0:
arr[i][col] = '#'
elif arr[i][col] == 6:
break
dfs(idx + 1)
# 좌
arr = copy.deepcopy(temp)
for i in range(col -1, -1, -1):
if arr[row][i] == 0:
arr[row][i] = '#'
elif arr[row][i] == 6:
break
dfs(idx + 1)
# 우
arr = copy.deepcopy(temp)
for i in range(col + 1, M):
if arr[row][i] == 0:
arr[row][i] = '#'
elif arr[row][i] == 6:
break
dfs(idx + 1)
elif value == 2:
# 상, 하
for i in range(row - 1, -1, -1):
if arr[i][col] == 0:
arr[i][col] = '#'
elif arr[i][col] == 6:
break
for i in range(row + 1, N):
if arr[i][col] == 0:
arr[i][col] = '#'
elif arr[i][col] == 6:
break
dfs(idx + 1)
# 좌, 우
arr = copy.deepcopy(temp)
for i in range(col -1, -1, -1):
if arr[row][i] == 0:
arr[row][i] = '#'
elif arr[row][i] == 6:
break
for i in range(col + 1, M):
if arr[row][i] == 0:
arr[row][i] = '#'
elif arr[row][i] == 6:
break
dfs(idx + 1)
elif value == 3:
# 상, 우
for i in range(row - 1, -1, -1):
if arr[i][col] == 0:
arr[i][col] = '#'
elif arr[i][col] == 6:
break
for i in range(col + 1, M):
if arr[row][i] == 0:
arr[row][i] = '#'
elif arr[row][i] == 6:
break
dfs(idx + 1)
# 우, 하
arr = copy.deepcopy(temp)
for i in range(col + 1, M):
if arr[row][i] == 0:
arr[row][i] = '#'
elif arr[row][i] == 6:
break
for i in range(row + 1, N):
if arr[i][col] == 0:
arr[i][col] = '#'
elif arr[i][col] == 6:
break
dfs(idx + 1)
# 하, 좌
arr = copy.deepcopy(temp)
for i in range(row + 1, N):
if arr[i][col] == 0:
arr[i][col] = '#'
elif arr[i][col] == 6:
break
for i in range(col -1, -1, -1):
if arr[row][i] == 0:
arr[row][i] = '#'
elif arr[row][i] == 6:
break
dfs(idx + 1)
# 좌, 상
arr = copy.deepcopy(temp)
for i in range(col -1, -1, -1):
if arr[row][i] == 0:
arr[row][i] = '#'
elif arr[row][i] == 6:
break
for i in range(row - 1, -1, -1):
if arr[i][col] == 0:
arr[i][col] = '#'
elif arr[i][col] == 6:
break
dfs(idx + 1)
elif value == 4:
# 좌, 상, 우
for i in range(col -1, -1, -1):
if arr[row][i] == 0:
arr[row][i] = '#'
elif arr[row][i] == 6:
break
for i in range(row - 1, -1, -1):
if arr[i][col] == 0:
arr[i][col] = '#'
elif arr[i][col] == 6:
break
for i in range(col + 1, M):
if arr[row][i] == 0:
arr[row][i] = '#'
elif arr[row][i] == 6:
break
dfs(idx + 1)
# 상, 우, 하
arr = copy.deepcopy(temp)
for i in range(row - 1, -1, -1):
if arr[i][col] == 0:
arr[i][col] = '#'
elif arr[i][col] == 6:
break
for i in range(col + 1, M):
if arr[row][i] == 0:
arr[row][i] = '#'
elif arr[row][i] == 6:
break
for i in range(row + 1, N):
if arr[i][col] == 0:
arr[i][col] = '#'
elif arr[i][col] == 6:
break
dfs(idx + 1)
# 우, 하, 좌
arr = copy.deepcopy(temp)
for i in range(col + 1, M):
if arr[row][i] == 0:
arr[row][i] = '#'
elif arr[row][i] == 6:
break
for i in range(row + 1, N):
if arr[i][col] == 0:
arr[i][col] = '#'
elif arr[i][col] == 6:
break
for i in range(col -1, -1, -1):
if arr[row][i] == 0:
arr[row][i] = '#'
elif arr[row][i] == 6:
break
dfs(idx + 1)
# 하, 좌, 상
arr = copy.deepcopy(temp)
for i in range(row + 1, N):
if arr[i][col] == 0:
arr[i][col] = '#'
elif arr[i][col] == 6:
break
for i in range(col -1, -1, -1):
if arr[row][i] == 0:
arr[row][i] = '#'
elif arr[row][i] == 6:
break
for i in range(row - 1, -1, -1):
if arr[i][col] == 0:
arr[i][col] = '#'
elif arr[i][col] == 6:
break
dfs(idx + 1)
else:
# 상
for i in range(row - 1, -1, -1):
if arr[i][col] == 0:
arr[i][col] = '#'
elif arr[i][col] == 6:
break
# 하
for i in range(row + 1, N):
if arr[i][col] == 0:
arr[i][col] = '#'
elif arr[i][col] == 6:
break
# 좌
for i in range(col -1, -1, -1):
if arr[row][i] == 0:
arr[row][i] = '#'
elif arr[row][i] == 6:
break
# 우
for i in range(col + 1, M):
if arr[row][i] == 0:
arr[row][i] = '#'
elif arr[row][i] == 6:
break
dfs(idx + 1)
if __name__ == "__main__":
# input
N, M = map(int, sys.stdin.readline().split()) # 세로, 가로
arr = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
# CCTY 위치 가져오기
position = []
for i in range(N):
for j in range(M):
if arr[i][j] != 0 and arr[i][j] != 6:
position.append(([arr[i][j], i, j]))
min_area = sys.maxsize
dfs(0)
print(min_area)728x90
'알고리즘 풀이 > 백준' 카테고리의 다른 글
| [ 백준 2589 ] 보물섬 - Python (4) | 2020.06.11 |
|---|---|
| [ 백준 16234 ] 인구 이동 - Python (0) | 2020.06.10 |
| [ 백준 3055 ] 탈출 - Python (0) | 2020.06.09 |
| [ 백준 1107 ] 리모컨 - Python (8) | 2020.06.09 |
| [ 백준 1916 ] 최소비용 구하기 - Python (2) | 2020.06.08 |