문제

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

해설

5종류의 CCTV를 적절히 회전해서 CCTV 사각지대의 최소 크기를 구하는 문제입니다.
각 CCTV가 한 번에 볼 수 있는 방향은 다음과 같습니다.

• 1번 : 1방향
• 2번 : 180° 간격으로 2방향
• 3번 : 90° 간격으로 2방향
• 4번 : 90° 간격으로 3방향
• 5번 : 90° 간격으로 4방향

CCTV는 90° 간격으로만 회전할 수 있으며, CCTV는 통과해서 볼 수 있지만 벽 너머는 보지 못합니다.

시간복잡도 계산

최대 8개의 CCTV가 있고, 각 CCTV를 4방향으로 회전하는데 최대 $4^8 = 65536$ 가 소요됩니다. 각각의 바라본 방향으로 확인을 하는데 최대 $max(N, M) \times 4$ 가 소요됩니다. $1 \leq N, M \leq 8$ 이므로, 총 uptime은 $65536 \times max(N, M) \times 4$ 입니다. 따라서 단순히 Brute-force로도 충분히 해결 가능합니다.

구현

입력을 받을 때, CCTV의 위치와 종류는 따로 저장해둡니다.

먼저, 각 CCTV에 대하여 4방향으로 회전시켰을 때 visit 배열을 사용해서 볼 수 있는 범위를 체크합니다. 모든 CCTV를 배치했을 때 사각지대의 크기를 확인한 뒤, 체크했던 visit 배열을 되돌립니다.

여기서 CCTV가 볼 수 있는 방향을 bitmask로 vector에 정의해두면 편리합니다.

소스 코드

http://boj.kr/asdfghjkl1234567890

코멘트

Bitmasking에 좀 더 친숙해져야겠습니다. 5종류의 CCTV 시야를 구현하는 아이디어를 떠올리는데 쉽지 않았습니다.

---

참고