[삼성역량테스트] 15683 감시

 

풀이일시 : 2020-10-17

​

문제 :

스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감시할 수 있는 방법은 다음과 같다.

 

 

1번 CCTV는 한 쪽 방향만 감시할 수 있다. 2번과 3번은 두 방향을 감시할 수 있는데, 2번은 감시하는 방향이 서로 반대방향이어야 하고, 3번은 직각 방향이어야 한다. 4번은 세 방향, 5번은 네 방향을 감시할 수 있다.

CCTV는 감시할 수 있는 방향에 있는 칸 전체를 감시할 수 있다. 사무실에는 벽이 있는데, CCTV는 벽을 통과할 수 없다. CCTV가 감시할 수 없는 영역은 사각지대라고 한다.

CCTV는 회전시킬 수 있는데, 회전은 항상 90도 방향으로 해야 하며, 감시하려고 하는 방향이 가로 또는 세로 방향이어야 한다.

지도에서 0은 빈 칸, 6은 벽, 1~5는 CCTV의 번호이다. 위의 예시에서 1번의 방향에 따라 감시할 수 있는 영역을 '#'로 나타내면 아래와 같다.

 

CCTV는 벽을 통과할 수 없기 때문에, 1번이 → 방향을 감시하고 있을 때는 6의 오른쪽에 있는 벽을 감시할 수 없다.

 

위의 예시에서 감시할 수 있는 방향을 알아보면 아래와 같다.

 

CCTV는 CCTV를 통과할 수 있다. 아래 예시를 보자.

위와 같은 경우에 2의 방향이 ↕ 3의 방향이 ←와 ↓인 경우 감시받는 영역은 다음과 같다.

사무실의 크기와 상태, 그리고 CCTV의 정보가 주어졌을 때, CCTV의 방향을 적절히 정해서, 사각 지대의 최소 크기를 구하는 프로그램을 작성하시오.

 

 

입력 :

첫째 줄에 사무실의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 8)

둘째 줄부터 N개의 줄에는 사무실 각 칸의 정보가 주어진다. 0은 빈 칸, 6은 벽, 1~5는 CCTV를 나타내고, 문제에서 설명한 CCTV의 종류이다.

CCTV의 최대 개수는 8개를 넘지 않는다.

ex)

4 6

0 0 0 0 0 0

0 0 0 0 0 0

0 0 1 0 6 0

0 0 0 0 0 0

​

​

출력 :

첫째 줄에 사각 지대의 최소 크기를 출력한다.

ex)

20

​

​

풀이 :

회전의 모든 경우를 탐색해주는 BF를 이용한다.

1번 cctv : 4가지 경우의 수

2번 cctv : 2가지 경우의 수

3번 cctv : 4가지 경우의 수

4번 cctv : 4가지 경우의 수

5번 cctv : 1가지 경우의 수

 

#include <iostream>
#include <vector>

#define MAX 8
#define INF 987654321

using namespace std;

int map[MAX][MAX];

vector<int> cctv;
vector<pair<int, int>> cctvLocation;

int N, M;
int ans = INF;

void MapCopy(int(*a)[MAX], int(*b)[MAX]) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            a[i][j] = b[i][j];
        }
    }
}

void spread(int dir, int x, int y) {
    //상
    if (dir == 0) {
        int ny = y - 1;
        if (ny < 0) return;
        if (map[ny][x] == 6) return;
        map[ny][x] = 9;
        spread(0, x, ny);
    }
    //우
    else if (dir == 1) {
        int nx = x + 1;
        if (nx > M - 1) return;
        if (map[y][nx] == 6) return;
        map[y][nx] = 9;
        spread(1, nx, y);
    }
    //하
    else if (dir == 2) {
        int ny = y + 1;
        if (ny > N - 1) return;
        if (map[ny][x] == 6) return;
        map[ny][x] = 9;
        spread(2, x, ny);
    }
    //좌
    else {
        int nx = x - 1;
        if (nx < 0) return;
        if (map[y][nx] == 6) return;
        map[y][nx] = 9;
        spread(3, nx, y);
    }
}

void check() {
    int cnt = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (map[i][j] == 0) {
                cnt += 1;
            }
        }
    }
    if (cnt < ans)
        ans = cnt;
}

void dfs(int cnt) {
    if (cnt > (int)cctv.size() - 1) { //만약 cnt가 cctv갯수를 다 탐색했다면
        //사각지대 검사
        check();
        return;
    }
    int kind = cctv[cnt]; //몇번 cctv인가
    int x = cctvLocation[cnt].first; //cctv 좌표
    int y = cctvLocation[cnt].second; //cctv 좌표

    int temp[MAX][MAX];

    //1번 cctv는 4방향
    if (kind == 1) {
        for (int i = 0; i < 4; i++) {
            MapCopy(temp, map); //map을 temp에 복사
            spread(i, x, y); //뻗어나가는 방향
            dfs(cnt + 1); //cctv 배열에있는 그다음 cctv를 찾아서 dfs
            MapCopy(map, temp); //다시 map으로 돌려놓기
        }
    }
    //2번 cctv는 2방향
    else if (kind == 2) {
        for (int i = 0; i < 2; i++) {
            MapCopy(temp, map);
            spread(i, x, y);
            spread(i + 2, x, y);
            dfs(cnt + 1);
            MapCopy(map, temp);
        }
    }
    //3번 cctv는 4방향
    else if (kind == 3) {
        for (int i = 0; i < 4; i++) {
            MapCopy(temp, map);
            spread(i, x, y);
            spread((i + 1) % 4, x, y);
            dfs(cnt + 1);
            MapCopy(map, temp);
        }
    }
    //4번 cctv는 4방향
    else if (kind == 4) {
        for (int i = 0; i < 4; i++) {
            MapCopy(temp, map);
            spread(i, x, y);
            spread((i + 1) % 4, x, y);
            spread((i + 2) % 4, x, y);
            dfs(cnt + 1);
            MapCopy(map, temp);
        }
    }
    //5번 cctv는 방향 변경x
    else {
        MapCopy(temp, map);
        for (int i = 0; i < 4; i++) {
            spread(i, x, y);
        }
        dfs(cnt + 1);
        MapCopy(map, temp);
    }
}

int main() {
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            int temp;
            cin >> temp;
            map[i][j] = temp;
            if (temp != 0 && temp != 6) { //입력된 temp가 벽X 빈칸X cctv이면
                cctv.push_back(temp); //cctv[]
                cctvLocation.push_back(make_pair(j, i)); //cctv의 위치도 저장
            }
        }
    }
    //map 입력완료 후
    dfs(0); //dfs(cnt=0)으로 시작 
    cout << ans << endl;
    return 0;
}
​