[백준 - 15683] 감시 - C++

분류: 백트래킹, 시뮬레이션, 완전탐색 /

 

문제

문제 링크

문제 설명

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

1번	2번	3번	4번	5번

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

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

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

0 0 0 0 0 0
0 0 0 0 0 0
0 0 1 0 6 0
0 0 0 0 0 0

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

0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 # 6 0 0 0 0 0 0 0	0 0 0 0 0 0 0 0 0 0 0 0 # # 1 0 6 0 0 0 0 0 0 0	0 0 # 0 0 0 0 0 # 0 0 0 0 0 1 0 6 0 0 0 0 0 0 0	0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 6 0 0 0 # 0 0 0
→	←	↑	↓

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

0 0 0 0 0 0
0 2 0 0 0 0
0 0 0 0 6 0
0 6 0 0 2 0
0 0 0 0 0 0
0 0 0 0 0 5

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

0 0 0 0 0 # # 2 # # # # 0 0 0 0 6 # 0 6 # # 2 # 0 0 0 0 0 # # # # # # 5	0 0 0 0 0 # # 2 # # # # 0 0 0 0 6 # 0 6 0 0 2 # 0 0 0 0 # # # # # # # 5	0 # 0 0 0 # 0 2 0 0 0 # 0 # 0 0 6 # 0 6 # # 2 # 0 0 0 0 0 # # # # # # 5	0 # 0 0 0 # 0 2 0 0 0 # 0 # 0 0 6 # 0 6 0 0 2 # 0 0 0 0 # # # # # # # 5
왼쪽 상단 2: ↔, 오른쪽 하단 2: ↔	왼쪽 상단 2: ↔, 오른쪽 하단 2: ↕	왼쪽 상단 2: ↕, 오른쪽 하단 2: ↔	왼쪽 상단 2: ↕, 오른쪽 하단 2: ↕

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

0 0 2 0 3
0 6 0 0 0
0 0 6 6 0
0 0 0 0 0

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

# # 2 # 3
0 6 # 0 #
0 0 6 6 #
0 0 0 0 #

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

입력

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

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

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

출력

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

 

풀이

- 내 풀이(백트래킹 완전 탐색)

#include <iostream>
#include <vector>
using namespace std;

struct xy { int x, y; };
int N, M, ans, zeros;
int board[8][8];
vector<xy> CCTV[6];
vector<vector<int>> ways[6] = {
    {},
    {{0}, {1}, {2}, {3}},
    {{0, 2}, {1, 3}},
    {{0, 1}, {1, 2}, {2, 3}, {3, 0}},
    {{0, 1, 2}, {1, 2, 3}, {2, 3, 0}, {3, 0, 1}},
    {{0, 1, 2, 3}},
};
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};

bool isWall(int x, int y) { 
    return x<0 || x>=N || y<0 || y>=M || board[x][y] == 6;
}
int replace(int dir, int x, int y, int before, int after) {
    int cnt = 0;
    while(true) {
        x += dx[dir]; 
        y += dy[dir];
        if(isWall(x, y)) return cnt;
        if(board[x][y] == before) {
            board[x][y] = after;
            cnt++;
        }
    }
}
void backTracking(int kind, int cur) {
    if(zeros == 0) {
        cout << 0;
        exit(0);
    }
    if(CCTV[kind].size() == cur) {
        if(kind > 1) return backTracking(kind - 1, 0);
        if(ans > zeros) ans = zeros;
        return;
    }
    auto [x, y] = CCTV[kind][cur];
    for(auto way : ways[kind]) {
        for(int dir : way)
            zeros -= replace(dir, x, y, 0, 100+10*x+y);
        backTracking(kind, cur + 1);
        for(int dir : way)
            zeros += replace(dir, x, y, 100+10*x+y, 0);
    }
}
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> N >> M;
    for(int i=0; i<N; i++) {
        for(int j=0; j<M; j++) {
            cin >> board[i][j];
            if(board[i][j] == 0) zeros++;
            else if(0 < board[i][j] && board[i][j] < 6)
                CCTV[board[i][j]].push_back({i, j});
        }
    }
    ans = zeros;
    backTracking(5, 0);
    cout << ans;
}

백트래킹을 이용한 완전 탐색

# CCTV 분류

CCTV를 종류 별로 나누어 저장하고 종류에 따라 가능한 설치 방법(`ways`)으로 가지를 치며 백트래킹을 한다.

종류별로 나누지 않고 vector에 모두 담아서 처리 할 수 도 있지만 `CCTV 5`의 경우, 한번 칠하고 다시 back tracking 할 필요가 없어서 가장 처음에 칠해놓고 시작하고 싶었다.

종류를 나누지 않고 백트래킹을 수행하면 코드는 아래와 같다.

#include <iostream>
#include <vector>
using namespace std;

struct xy { int x, y; };
int N, M, ans, zeros;
int board[8][8];
vector<xy> CCTV;
vector<vector<int>> ways[6] = {
    {},
    {{0}, {1}, {2}, {3}},
    {{0, 2}, {1, 3}},
    {{0, 1}, {1, 2}, {2, 3}, {3, 0}},
    {{0, 1, 2}, {1, 2, 3}, {2, 3, 0}, {3, 0, 1}},
    {{0, 1, 2, 3}},
};
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};

bool isWall(int x, int y) { 
    return x<0 || x>=N || y<0 || y>=M || board[x][y] == 6;
}
int replace(int dir, int x, int y, int before, int after) {
    int cnt = 0;
    while(true) {
        x += dx[dir]; 
        y += dy[dir];
        if(isWall(x, y)) return cnt;
        if(board[x][y] == before) {
            board[x][y] = after;
            cnt++;
        }
    }
}
void backTracking(int cur) {
    if(zeros == 0) {
        cout << 0;
        exit(0);
    }
    if(CCTV.size() == cur) {
        if(ans > zeros) ans = zeros;
        return;
    }
    auto [x, y] = CCTV[cur];
    for(auto way : ways[board[x][y]]) {
        for(int dir : way)
            zeros -= replace(dir, x, y, 0, 100+10*x+y);
        backTracking(cur + 1);
        for(int dir : way)
            zeros += replace(dir, x, y, 100+10*x+y, 0);
    }
}
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> N >> M;
    for(int i=0; i<N; i++) {
        for(int j=0; j<M; j++) {
            cin >> board[i][j];
            if(board[i][j] == 0) zeros++;
            else if(0 < board[i][j] && board[i][j] < 6)
                CCTV.push_back({i, j});
        }
    }
    ans = zeros;
    backTracking(0);
    cout << ans;
}

 

# 롤백(진법)

롤백 과정에서 자기가 마킹한 부분만 다시 원상 복구 시키는 것이 중요하다. 예를들어 (0, 0) 3에 의해 0행, 0열이 모두 7로 마킹 되어있는 상태에서 (2, 2) 2의 두가지 경우의 수를 확인하는 상황을 가정해보자.

2가 마킹한 부분만 롤백하지 않고 7을 모두 롤백하면 아래 처럼 (0, 2)까지 0으로 만들어 버리는 상황이 발생한다. 

3 7 7 7 7        3 7 7 7 7        3 7 0 7 7
7 0 0 0 0        7 0 7 0 0        7 0 0 0 0
7 0 2 0 0   ->   7 0 2 0 0   ->   7 7 2 7 7
7 0 0 0 0        7 0 7 0 0        7 0 0 0 0
7 0 0 0 0        7 0 7 0 0        7 0 0 0 0

이를 해결하기 위해 (x, y)는 `100 + 10*x + y`로 마킹했다. x, y가 최대 7이므로 한자리여서 10진법의 자리 숫자로 사용할 수 있고 100을 더한 이유는 (0, 0), (0, 1), ... , (0, 6)의 경우 100을 더하지 않으면 스페셜 값과 구분할 수 없기에 100을 더해 겹치지 않도록 했다.

마킹으로 어떤 CCTV가 마킹한 것인지 구분이 가능하다.

 

# repace cnt

매번 마킹을 하고 0의 마킹한 만큼 0의 수를 줄이고(`zeros -= replace()`)

롤백을 하고 롤백한 만큼 0의 수를 늘려서(`zeros += replace()`) 항상 0의 수를 트래킹한다.

`zeros`가 0이 되면 항상 최솟값이므로 프로그램을 종료하고

리프에 도달하면 `zeros`의 최솟값 `ans`와 비교해 답을 누적한다.

 

- 다른 사람 풀이(비트를 이용한 완전 탐색)

#include <iostream>
#include <vector>
using namespace std;

struct xy {int x, y;};
int N, M;
int board1[8][8];
int board2[8][8];
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};

bool isWall(int x, int y) { 
    return x<0 || x>=N || y<0 || y>=M || board2[x][y] == 6;
}
int replace(int x, int y, int dir) {
    dir %= 4;
    int cnt = 0;
    while(true) {
        x += dx[dir]; 
        y += dy[dir];
        if(isWall(x, y)) break;
        if(board2[x][y]) continue;
        board2[x][y] = 7;
        cnt++;
    }
    return cnt;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> N >> M;
    int zeros = 0;
    vector<xy> CCTV;
    for(int i=0; i<N; i++) {
        for(int j=0; j<M; j++) {
            cin >> board1[i][j];
            if(board1[i][j] == 0) zeros++;
            else if(board1[i][j] == 6) continue;
            else CCTV.push_back({i, j});
        }
    }

    int ans = zeros;
    for(int tmp=0; tmp < (1 << (2 * CCTV.size())); tmp++) {
        for(int i=0; i<N; i++)
            for(int j=0; j<M; j++)
                board2[i][j] = board1[i][j];

        int cur = tmp;
        int curZeros = zeros;
        for(int i=0; i<CCTV.size(); i++) {
            int dir = cur % 4;
            cur /= 4;

            auto [x, y] = CCTV[i];
            if(board2[x][y] == 1) {
                curZeros -= replace(x, y, dir);
            } 
            else if(board2[x][y] == 2) {
                curZeros -= replace(x, y, dir);
                curZeros -= replace(x, y, dir + 2);
            }
            else if(board2[x][y] == 3) {
                curZeros -= replace(x, y, dir);
                curZeros -= replace(x, y, dir + 1);
            }
            else if(board2[x][y] == 4) {
                curZeros -= replace(x, y, dir);
                curZeros -= replace(x, y, dir + 1);
                curZeros -= replace(x, y, dir + 2);
            }
            else {
                curZeros -= replace(x, y, dir);
                curZeros -= replace(x, y, dir + 1);
                curZeros -= replace(x, y, dir + 2);
                curZeros -= replace(x, y, dir + 3);
            }
        }
        if(curZeros < ans) ans = curZeros;
    }
    cout << ans;
}

다른 사람의 코드를 조금 각색했다.

풀이를 해석해보면 다음과같다.

CCTV를 설치하는 방향은 최대 4개이다. 이를 4진법으로 표현 할 수 있다.

예) `CCTV 1`이 남쪽을 보면 0, 서쪽을 보면 1, 북쪽을 보면 2, 동쪽을 보면 3

 

따라서 k개의 CCTV는 k자리수의 4진법으로 표현가능하다.

예를 들어 5개의 1번 CCTV가 있다고 가정했을 때 `02130`은 k개의 CCTV가 순서대로 `남북서동남`쪽을 보고있는 상황이다.

볼 수 있는 방향이 4개 미만인 2번, 5번 CCTV의 경우, 위 코드에서는 중복해서 계산했지만 0일때만 계산하는 식으로 최적화가 가능하다.

 

k자리수의 4진법은 10진법으로 4^k이고 이는 2^2k다.

따라서 첫번째 for문의 `tmp < (1 << (CCTV.size() << 1))`는 2^{2*CCTV.size()}는 CCTV의 수 만큼 자리수를 갖는 4진법이고 이는 전체 경우의 수를 나타낸다.

`tmp` 또는 `cur`은 현재 경우의 수를 나타낸다. 모든 CCTV가 어떤 방향을 보고 있는지 결정 된 상태이다.

4진법 `tmp or cur`의 하나의 비트는 하나의 CCTV에 대응되므로 `dir = cur/4;   cur /= 4`로 끝 비트 하나를 잘라 해당 CCTV의 방향(`dir`)로 사용한다.

 

하나의 경우의 수(백트래킹에서 리프 노드)마다 `board1` 원본을 `board2`에 덮어쓰며 사용하기 때문에 롤백과정이 필요없다. 처음부터 리프노드의 상황이 주어지기 때문이다.

 

 

서로 독립적인 개체들의 상태를 완전탐색 할 백트래킹과 경우 비트를 이용한 완전탐색 방법을 모두 고려해 봐야할 것 같다.

 

# 중복을 어느정도 제거한 코드

#include <iostream>
#include <vector>
using namespace std;

struct xy {int x, y;};
int N, M; 
int board[8][8], curBoard[8][8];;
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};

int fill(int x, int y, int dir) {
    dir %= 4;
    int cnt = 0;
    while(true) {
        x += dx[dir]; y += dy[dir];
        if(x<0 || x>=N || y<0 || y>=M || curBoard[x][y] == 6) 
            return cnt;
        if(curBoard[x][y] == 0) {
            curBoard[x][y] = 7;
            cnt++;
        }
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> N >> M;
    vector<xy> CCTV;
    int initZeros = 0;
    for(int i=0; i<N; i++) {
        for(int j=0; j<M; j++) {
            cin >>board[i][j];
            if(board[i][j] == 0) initZeros++;
            else if(board[i][j] == 6) continue;
            else CCTV.push_back({i, j});
        }
    }

    int ans = initZeros;
    for(int tmp = 0; tmp < (1 << (CCTV.size() << 1)); tmp++) {
        int cur = tmp;
        int curZeros = initZeros;
        for(int i=0; i<N; i++)
            for(int j=0; j<M; j++)
                curBoard[i][j] = board[i][j];
        
        for(auto[x, y] : CCTV) {
            int dir = cur % 4;
            cur /= 4;
            
            if(curBoard[x][y] == 1) {
                curZeros -= fill(x, y, dir);
            }
            else if(curBoard[x][y] == 2) {
                if(dir > 1) break;
                curZeros -= fill(x, y, dir);
                curZeros -= fill(x, y, dir + 2);
            }
            else if(curBoard[x][y] == 3) {
                curZeros -= fill(x, y, dir);
                curZeros -= fill(x, y, dir + 1);
            }
            else if(curBoard[x][y] == 4) {
                curZeros -= fill(x, y, dir);
                curZeros -= fill(x, y, dir + 1);
                curZeros -= fill(x, y, dir + 2);
            }
            else {
                if(dir != 0) break;
                curZeros -= fill(x, y, dir);
                curZeros -= fill(x, y, dir + 1);
                curZeros -= fill(x, y, dir + 2);
                curZeros -= fill(x, y, dir + 3);
            }
        }
        if(curZeros < ans) ans = curZeros;
    }
    cout << ans;
}