목록백준 15683 C++ (1)

1일1알

백준 15683번 감시 C++

은근히 고려해야 할게 많은 쉽지는 않은 구현 문제이다. 각각의 cctv마다 감시할 수 있는 경우의 수가 다르다. 예를 들면, 1번 cctv는 상, 하, 좌, 우 4가지 경우를 감시할 수 있고, 2번 cctv는 상하, 좌우 2가지 경우를 감시할 수 있다. 이 경우들을 비트로 만들어서 저장하였다. 위, 오른쪽, 아래, 왼쪽 순서로 저장했고 감시할 수 있으면 1, 못하면 0으로 저장했다. 2번 cctv의 경우는 상하, 좌우 2가지 경우가 있기 때문에 1010, 0101 두 개를 저장했다. 다음은 백트래킹을 이용하여 모든 경우를 탐색했는데, 중간에 마스크를 이용해서 감시할 수 있는 지역을 알아냈다. 마스크는 1000부터 시작하여 오른쪽으로 한 칸씩 옮겨가는데, 각 경우마다 cctv와 &연산을 해서 0이 아니라면..
알고리즘 2022. 1. 7. 12:55
이전 Prev 1 Next 다음