알고리즘/백준
[백준 15683] 감시
최성훈
2019. 10. 10. 19:10
반응형
이 문제는 브루트 포스 문제이다.
다음과 같은 감시카메라로 감시를 할 때, 주어진 맵에서 최소의 사각지대를 구해야한다.
감시카메라의 종류는 다음과 같다.
각 종류의 감시카메라가 90도마다 회전할 때의 최소 사각지대를 구해야한다.
다음 그림을 보면 이해할 수 있다.
위 그림을 설명하자면, CCTV 리스트에 있는 모든 카메라들에 대해서 4번씩 회전시키고, solution()함수를 재귀적으로 실행시킨다. 이때의 매개변수는 현재 CCTV 리스트와 그 index이다.
1. 리스트 내의 index가 0인 1번 CCTV의 모든 회전에 대해서 재귀적으로 탐색을 한다. (그림에서는 1번 CCTV를 4번 회전시킨다.)
2. 1번 CCTV의 각 회전에 대해서 리스트 내의 index가 1인 2번 CCTV의 모든 회전에 대해서 재귀적으로 탐색을 한다. (그림에서는 2번 CCTV를 4번 회전시킨다.)
...
이를 재귀적으로 표현한 부분으로, 모든 감시카메라가 4번씩 회전하는 모든 경우의 수는 111~114번째 줄에 구현되어 있다.
up, right, down, left 함수는 좌표가 주어졌을 때, 그 좌표로부터 상,하,좌,우로 감시하는 함수이다. (감시되는 영역은 2차원 배열에서 -1로 표시된다.)
47~100번째 줄은, DFS로 모든 경우의 수마다, 주어진 맵에서 사각지대를 구하는 부분이다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 | import sys from copy import deepcopy n, m = map(int, sys.stdin.readline().split()) board = [list(map(int, sys.stdin.readline().split())) for c in range(n)] def up(temp_board, r, c): count = 1 for i in range(r, -1, -1): if temp_board[i][c] == 6: break temp_board[i][c] = -1 return count def right(temp_board, r, c): count = 1 for j in range(c, m, 1): if temp_board[r][j] == 6: break temp_board[r][j] = -1 return count def down(temp_board, r, c): count = 1 for i in range(r, n, 1): if temp_board[i][c] == 6: break temp_board[i][c] = -1 return count def left(temp_board, r, c): count = 1 for j in range(c, -1, -1): if temp_board[r][j] == 6: break temp_board[r][j] = -1 return count def solution(idx, obs_list): global answer temp_board = deepcopy(board) if idx == list_size: # count all detection area for ((r, c), observer, offset) in obs_list: if observer == 1: if offset == 0: right(temp_board, r, c) elif offset == 1: down(temp_board, r, c) elif offset == 2: left(temp_board, r, c) else: up(temp_board, r, c) elif observer == 2: if offset == 0 or offset == 2: right(temp_board, r, c) left(temp_board, r, c) elif offset == 1 or offset == 3: up(temp_board, r, c) down(temp_board, r, c) elif observer == 3: if offset == 0: up(temp_board, r, c) right(temp_board, r, c) elif offset == 1: right(temp_board, r, c) down(temp_board, r, c) elif offset == 2: down(temp_board, r, c) left(temp_board, r, c) else: left(temp_board, r, c) up(temp_board, r, c) elif observer == 4: if offset == 0: up(temp_board, r, c) right(temp_board, r, c) down(temp_board, r, c) elif offset == 1: right(temp_board, r, c) down(temp_board, r, c) left(temp_board, r, c) elif offset == 2: down(temp_board, r, c) left(temp_board, r, c) up(temp_board, r, c) else: left(temp_board, r, c) up(temp_board, r, c) right(temp_board, r, c) else: up(temp_board, r, c) right(temp_board, r, c) left(temp_board, r, c) down(temp_board, r, c) # get the minimum space count = 0 for r in range(n): for c in range(m): if temp_board[r][c] == 0: count += 1 answer = min(answer, count) return answer # traverse all occasion for i in range(4): obs_list[idx][2] = i solution(idx + 1, obs_list) # make a list of observers observer_list, list_size = list(), 0 for i in range(n): for j in range(m): if 0 < board[i][j] < 6: observer_list.append([(i, j), board[i][j], 0]) list_size += 1 answer = sys.maxsize solution(0, observer_list) print(answer) | cs |
반응형