[BOJ / C++] 감시 (시뮬레이션)

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

 

> 방법 1: 4진법을 이용한 완전탐색

1. 코드

#include <bits/stdc++.h>
using namespace std;

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

void upd(int x, int y, int dir, vector<vector<int>>& board, int n, int m) {
    dir %= 4;
    while (true) {
        x += dx[dir];
        y += dy[dir];
        
        // 범위 벗어나거나 벽을 만나면 함수 종료
        if (x < 0 || x >= n || y < 0 || y >= m) return;
        if (board[x][y] == 6) return;

        if (board[x][y] != 0) continue; // cctv가 있는 경우
        board[x][y] = 7; // 빈칸을 7로 표시
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    
    int n, m;
    cin >> n >> m;

    int mn = 0;

    vector<vector<int>> inpBoard(n, vector<int>(m, 0));
    vector<vector<int>> board(n, vector<int>(m, 0));
    vector<pair<int, int>> cctv;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> inpBoard[i][j];
            if (inpBoard[i][j] > 0 && inpBoard[i][j] < 6) cctv.push_back({i, j});
            if (inpBoard[i][j] == 0) mn++;
        }
    }

    for (int tmp = 0; tmp < (1 << 2 * cctv.size()); tmp++) {
        // inputBoard 복사
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                board[i][j] = inpBoard[i][j];
            }
        }

        // 4진법으로 tmp에 해당하는 경우 계산
        int brute = tmp;
        for (int i = 0; i < cctv.size(); i++) {
            int dir = brute % 4;
            brute /= 4;

            int x, y;
            tie(x, y) = cctv[i];

            if (board[x][y] == 1) {
                upd(x, y, dir, board, n, m);
            }
            else if (board[x][y] == 2) {
                upd(x, y, dir, board, n, m);
                upd(x, y, dir+2, board, n, m);
            }
            else if (board[x][y] == 3) {
                upd(x, y, dir, board, n, m);
                upd(x, y, dir+1, board, n, m);
            }
            else if (board[x][y] == 4) {
                upd(x, y, dir, board, n, m);
                upd(x, y, dir+1, board, n, m);
                upd(x, y, dir+2, board, n, m);
            }
            else if (board[x][y] == 5) {
                upd(x, y, dir, board, n, m);
                upd(x, y, dir+1, board, n, m);
                upd(x, y, dir+2, board, n, m);
                upd(x, y, dir+3, board, n, m);
            }

        }

        // 사각지대 세기
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (board[i][j] == 0) cnt++;
            }
        }
        mn = min(mn, cnt);
    }

    cout << mn;
}

 

 

2. 분석

각 cctv가 바라보는 방향이 4가지가 있으므로 (전부다 4가지는 아니지만 최대 4가지이다.) 4진법에 대응해서 완전탐색이 가능하다. tmp < 4^cctv.size() 만큼 tmp를 증가시키면서 해당 tmp에 대해 dir = brute % 4; brute /=4;로 각 자릿수를 추출해 대응시켜 계산한다.

 

3. 시간복잡도

cctv 개수를 k라 하면, 각 경우가 4가지 경우가 있으므로 4^k이 되고 최대 8개 있을 수 있으므로 시간복잡도는 (4 * 8(upd 호출 횟수) * 8(upd에서 연산량) + 64(빈칸 확인)) * 4^8 = 20,971,520 < 10^8 이므로 시간내 통과가 가능하다.

 

 

> 방법 2: 백트래킹을 이용한 완전탐색

1. 코드

#include <bits/stdc++.h>
using namespace std;

int n, m;
int board[10][10];
int boardcheck[10][10];
int result = 1e9;

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

vector<pair<int, int>> cctv;

vector<vector<vector<int>>> cctvDir = {
	{},
	{{0}, {1}, {2}, {3}}, // 1번
	{{0, 2}, {1, 3}}, // 2번
	{{0, 1}, {1, 2}, {2, 3}, {3, 0}}, // 3번
	{{0, 1, 2}, {1, 2, 3}, {2, 3, 0}, {3, 0, 1}}, // 4번
	{{0, 1, 2, 3}} // 5번
};

void watch(int x, int y, int dir) {
	int nx = x + dx[dir];
	int ny = y + dy[dir];

	while (true) {
		if (nx < 0 || nx >= n || ny < 0 || ny >= m) break;
		if (boardcheck[nx][ny] == 6) break;
		if (boardcheck[nx][ny] == 0) boardcheck[nx][ny] = 7;
		nx += dx[dir];
		ny += dy[dir];
	}
}

void simulate(int depth) {
	if (depth == cctv.size()) {
		int cnt = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (boardcheck[i][j] == 0) cnt++;
			}
		}
		result = min(result, cnt);
		return;
	}

	int x = cctv[depth].first;
	int y = cctv[depth].second;
	int type = board[x][y];

	for (const auto& dirs: cctvDir[type]) {
		int backup[10][10];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				backup[i][j] = boardcheck[i][j];
			}
		}

		for (int d: dirs) watch(x, y, d);

		simulate(depth+1);

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				boardcheck[i][j] = backup[i][j];
			}
		}
	}
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			int inp;
			cin >> inp;
			board[i][j] = inp;
			boardcheck[i][j] = inp;
			if (1 <= board[i][j] && board[i][j] <= 5) cctv.push_back({i, j});
		}
	}

	simulate(0);

	cout << result;
}

 

 

2. 분석

백트래킹을 이용해 완전탐색으로 모든 경우를 계산한다. depth == cctv.size() 이면 모든 cctv에 대해 업데이트를 한 경우가 된다. cctvDir을 모두 저장하고 각 cctv의 type에 따라 해당 방향을 업데이트해서 계산한다.

 

3. 시간복잡도

시간복잡도는 동일하다. cctv 개수를 k라 하면, 각 경우가 4가지 경우가 있으므로 4^k이 되고 최대 8개 있을 수 있으므로 시간복잡도는 (4 * 8(upd 호출 횟수) * 8(upd에서 연산량) + 64(빈칸 확인)) * 4^8 = 20,971,520 < 10^8 이므로 시간내 통과가 가능하다.