A. 문제설명
https://www.acmicpc.net/problem/15683
문제에 대한 자세한 설명은 링크 참조
1. N * M 배열 크기의 사무실에 K개의 CCTV가 설치
2. 배열의 각 좌표에는 0: 빈칸, 1~5: CCTV, 6:벽이 주어짐
3. 각 CCTV는 아래와 같이 번호에 따라 감시할 수 있는 방향이 정해져 있다.
4. CCTV는 같은 CCTV를 통과할 수 있으며, 벽은 통과하지 못한다.
5. CCTV는 90도씩 회전이 가능하며 전방향중 가장 감시면적이 넓은 방향을 보게할 때, CCTV가 감시하지 못하는 사각지대 영역의 최소 구하기
B. 접근법
완전탐색과 시뮬레이션
먼저, CCTV의 모든 방향 조합을 구하고, 그 조합에 따라 구해지는 사각지대 영역을 계산하여 그 중 최소를 고르자
C. 풀이
1. 먼저 DFS로 CCTV의 모든 방향 조합을 구하자
2. 스트링 형태로 모아진 CCTV의 방향조합은 1,3,4의 경우 0/90/180/270도 회전의 경우를 보지만, 2의 경우 0/90도 회전만, 5번은 회전할 필요가 없다는 것을 고려하여 구현
3. K개의 CCTV에 대한 방향조합이 구해졌을 때, 해당 방향에서의 각 CCTV의 감시영역 크기를 구함
4. CCTV가 감시 못하는 사각지대의 영역 중 최소를 반환
D. 내 코드
