[BOJ] 15683. 감시

[문제]

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

15683번: 감시

[풀이]

 

1)  cctv가 한번에 탐색할 수 있는 방향은 정해져 있다. 

1번 - 1

2번 - 2

3번 - 2

4번 - 3

5번 - 4

 

2) cctv가 여러대 있을 때 각각 탐색할 수 있는 방향을 정해서 그 때의 최소 사각지대를 구하는 것이다. (각 cctv마다 모든 방향을 탐색한 후에 사각지대를 구하는 게 아님)

 

3) 칸에 적힌 수가 0인 칸은 빈칸이고 사각지대가 될 수 있는 칸이다. 1-5 : cctv, 6 - 벽 

 

4) cctv는 서로 통과할 수 있다. 

 

5) 두 가지 정수 배열을 만든다. 

tvCnt =>  각 cctv마다 한번에 탐색할 수 있는 방향의 개수 (만약 1번 cctv와 5번이 있을 때 1번은 한 방향, 5번은 4방향을 한번에 탐색해야하기 때문에)

 

tvDir => 각 cctv마다 탐색할 수 있는 방향 지정(상 우 하 좌 ) 

 

6) 재귀 호출을 사용한다. (cctv의 개수가 정해져 있고 완탐을 하기 위해서 )

dfs( 현재 탐색할 cctv의 인덱스 , 남은 사각지대의 개수 )

 

6-1) 종료 조건 => 모든 cctv를 탐색했을 때 (남은 사각지대의 개수를 리턴한다.

 

6-2) 현재 맵의 상태를 저장하는 게 중요하다. (c_map을 생성해서 맵의 상태를 보존한다.)

 

6-3) 두 개의 for 반복문을 사용한다. (1 => 상 하 좌 우 / 2 -> 각 cctv마다 한번에 탐색할 수 있는 방향의 개수만큼 반복)

탐색할 수 있는 방향은 4개이기 때문에  dir = (j+i) % 4 함으로서 올바른 범위 내의 방향을 탐색할 수 있도록 한다. 

 

6-4) 현재 나아갈 수 있는 방향이 맵의 범위를 벗어나지 않고 벽을 만나지 않았다면 계속 나아간다. (벽을 만날 때까지)

=> 사각지대의 개수를 줄여주고, 사각지대가 아닌 칸은 -1로 만들어준다. (맵의 변형 -> cctv의 방향을 바꿀 때마다 맵을 복원해줘야 하는 이유이다.)

 

6-5) 현재 cctv가 탐색할 수 있는 모든 방향을 탐색했다면 재귀호출을 해서 다른 cctv도 탐색하여 최소 사각지대를 구한다. 

#include <iostream> #include <vector> #include <cstring> using namespace std; int n, m; int map[9][9]; int tvCnt[6]={0,1,2,2,3,4}; //한번에 살펴볼 수 있는 방향의 개수 int tvDir[6][4] = {{},{0},{0,2},{0,1},{0,1,3}, {0,1,2,3}}; int dx[4] = {-1,0,1,0}, dy[4] = {0,1,0,-1}; typedef pair<int, int> pp; vector<pp> tvs; int ans = 65; //현재 cctv 인덱스, 남은 사각지대 개수 int min(const int &a, const int &b) { if (a > b) return b; return a; } void dfs(int idx, int res) { if (idx == tvs.size()) { ans = min(res, ans); return; } //cctv정보 int x = tvs[idx].first; int y = tvs[idx].second; int num= map[x][y]; int c_map[9][9]; memcpy(c_map, map, sizeof(map)); for (int i = 0; i < 4; i++) { //방향 전환 memcpy(map, c_map, sizeof(map)); int cnt = res; //남은 사각지대 개수 저장 for (int j = 0; j < tvCnt[num]; j++) { //한번에 볼 수 있는 방향의 개수만큼 반복 int dir = tvDir[num][j]; int nx = x + dx[(dir+i)%4]; int ny = y + dy[(dir+i)%4]; while(nx >= 0 && nx < n && ny >= 0 && ny < m && map[nx][ny] != 6) { if (!map[nx][ny]) { map[nx][ny] = -1; cnt--; } nx += dx[(dir+i)%4]; ny += dy[(dir+i)%4]; } } //한번에 볼 수 있는 방향 탐색 끝 dfs(idx+1, cnt); } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> m; int corners = 0; for (int i = 0; i < n; i++) { for(int j = 0; j< m; j++) { cin >> map[i][j]; if (1<= map[i][j] && map[i][j] <= 5) { tvs.push_back(pp(i, j)); } else if (!map[i][j]) corners++; } } dfs(0,corners); cout << ans << '\n'; return 0; }