[백준 15683번] 감시

문제 링크: https://www.acmicpc.net/problem/15683

15683번: 감시

<문제 풀이> 시뮬레이션

1번 cctv부터 n번 cctv까지 한 번씩 회전시켜보면서 모든 경우의 수를 다 해보면 되는 완전 탐색 문제입니다.

 

문제는 방향을 어떻게 처리할까 인데 각 CCTV의 방향을 분리해서 생각해보면 쉽게 문제를 해결할 수 있습니다.

 

int dx[4] = {0, -1, 0, 1}; //0 == right, 1 == up, 2 == left, 3 == down

int dy[4] = {1, 0, -1, 0};

 

dfs, bfs에서 위와 같이 4방향을 나타내는데 각 인덱스의 의미는 아래와 같습니다.

0번 인덱스는 오른쪽 방향

1번 인덱스는 위쪽 방향

2번 인덱스는 왼쪽 방향

3번 인덱스는 아래쪽 방향

 

 

 

이제 cctv로 방향을 표현해보겠습니다

1번	2번	3번	4번	5번

1번 cctv : right ( 0 index)

2번 cctv: left  + right (2 index + 0 index)

3번 cctv: up + right (1 index + 0 index)

4번 cctv: left + up + right (2 index + 1 index + 0 index)

5번 cctv: down + left + up + right (3 index + 2 index + 1 index + 0 index)

 

이제 cctv로 감시구역을 체크할 때 cctv의 방향을 분리해서 한 방향씩 검사를 해보면 됩니다.

그리고 회전할 때는 방향 인덱스의 값을 +1 해주면 끝입니다. 

/*dir 1증가하면 90도 회전*/

        if (cctv[x][y] == 1) {

            check(x, y, dir); //dir == 0 일때 right

        }

        else if (cctv[x][y] == 2) { 

            check(x, y, dir); //dir == 0 일때 right

            check(x, y, dir + 2); //dir == 0 일때 left

 

        }

        else if (cctv[x][y] == 3) {

            check(x, y, dir); //dir == 0 일때 right

            check(x, y, dir + 1); //dir == 0 일때 up

        }

        else if (cctv[x][y] == 4) {

            check(x, y, dir); //dir == 0 일때 right

            check(x, y, dir + 1); //dir == 0 일때 up

            check(x, y, dir + 2); //dir == 0 일때 left

 

        }

        else if (cctv[x][y] == 5) {

            check(x, y, dir); //dir == 0 일때 right

            check(x, y, dir + 1); //dir == 0 일때 up

            check(x, y, dir + 2); //dir == 0 일때 left

            check(x, y, dir + 3); //dir == 0 일때 down

 

        }

        solve(idx + 1); //다음 cctv 회전시키기

        for (int i = 0; i < N; i++) {

            for (int j = 0; j < M; j++) {

                cctv[i][j] = backup[i][j];

            }

        }

 

 

 

 

<C++ 소스 코드>

#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <utility>
#include <climits>
#include <cmath>
#include <deque>
#include <cstdlib>
using namespace std;
 
int dx[4] = {0, -1, 0, 1}; //0 == right, 1 == up, 2 == left, 3 == down
int dy[4] = {1, 0, -1, 0};
 
int N, M;
int cctv[8][8]; // 0 빈칸, 1 ~ 5 cctv, 6 벽
vector<pair<int, int> > cctv_pos;
int res = 64;
 
 
//x,y에 위치한 cctv가 dir방향을 감시
void check(int x, int y, int dir) {
    dir %= 4; //가능한 감시방향 right, up, left, down (0 ~ 3)
    while (true) {
        int nx = x + dx[dir];
        int ny = y + dy[dir];
        x = nx;
        y = ny;
        if (nx < 0 || ny < 0 || nx >= N || ny >= M)return;
        if (cctv[nx][ny] == 6) return;
        if (cctv[nx][ny] != 0) continue;
        cctv[nx][ny] = '#';
    }
}
 
 
//idx번째 cctv를 회전
void solve(int idx) {
    int cctv_cnt = cctv_pos.size();
    if (idx == cctv_cnt) { //모든 cctv를 다 확인했을 때
        int temp_res = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (cctv[i][j] == 0) temp_res++;
            }
        }
        res = min(res, temp_res);
        return;
    }
    int x = cctv_pos[idx].first;
    int y = cctv_pos[idx].second;
    int backup[8][8];
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            backup[i][j] = cctv[i][j];
        }
    }
    for (int dir = 0; dir < 4; dir++) { //4번까지 회전시켜본다
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                backup[i][j] = cctv[i][j];
            }
        }
        /*dir 1증가하면 90도 회전*/
        if (cctv[x][y] == 1) {
            check(x, y, dir); //dir == 0 일때 right
        }
        else if (cctv[x][y] == 2) { 
            check(x, y, dir); //dir == 0 일때 right
            check(x, y, dir + 2); //dir == 0 일때 left
 
        }
        else if (cctv[x][y] == 3) {
            check(x, y, dir); //dir == 0 일때 right
            check(x, y, dir + 1); //dir == 0 일때 up
        }
        else if (cctv[x][y] == 4) {
            check(x, y, dir); //dir == 0 일때 right
            check(x, y, dir + 1); //dir == 0 일때 up
            check(x, y, dir + 2); //dir == 0 일때 left
 
        }
        else if (cctv[x][y] == 5) {
            check(x, y, dir); //dir == 0 일때 right
            check(x, y, dir + 1); //dir == 0 일때 up
            check(x, y, dir + 2); //dir == 0 일때 left
            check(x, y, dir + 3); //dir == 0 일때 down
        }
        solve(idx + 1); //다음 cctv 회전시키기
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                cctv[i][j] = backup[i][j];
            }
        }
    }
}
 
 
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> cctv[i][j];
            if (cctv[i][j] >= 1 && cctv[i][j] <= 5) {
                cctv_pos.push_back({ i, j });     
            }
        }
    }
    solve(0);
    cout << res;
    
    return 0;
}