[ BOJ 오답노트 ] 15683 C++ : 감시

 

 

1. 문제 해결 과정

(1) 총 가능한 경우의 수 계산

1번 CCTV는 4가지, 2번 CCTV는 2가지, 3번 CCTV는 4가지, 4번 CCTV는 4가지, 5번 CCTV는 1가지가 가능하다. 모두 4의 약수로, 총 가능한 경우의 수는 4의 거듭제곱승이다. 이 때, 지수는 CCTV의 개수이다.

예를 들면 위와 같은 경우로 나타낼 수 있다. CCTV 1번과 4번으로 총 2대가 있을 때의 경우의 수는 4의 2승으로 총 16가지이다.

여기에서 드는 의문이 예를 들어서 1번과 2번이 있다고 했을 때 총 경우의 수는 4 곱하기 2로 8인데, 4의 2승으로 총 16번을 조사하는 것이 아닌지 생각할 수 있는데, 전체적으로 시간 복잡도를 봤을 때 그 연산이 있다고 해서 시간 초과가 발생하지 않으므로 4의 거듭제곱으로 진행한다.

 

이렇게 4의 거듭제곱으로 전체 경우의 수를 계산한 후에는 각 CCTV의 방향으로 하나씩 조사를 하는데, 4진법으로 변환하는 것이 핵심이다.

 

long long tot = 1;
for (int pow = 0; pow < size(cctv); pow++) tot *= 4;

 

일단 거듭제곱으로 만드는 방법으로는 여러가지가 있는데, pow라는 간편한 함수가 있다. 하지만 오버플로우가 되어서 이상한 값으로 만들어질수 있으니 안전하게 for문을 사용한다.

Left Shift로 거듭제곱을 구하는 방법도 있지만 가장 직관적이고 확실한 답을 위해서 for문으로 구현한다.

 

4의 거듭제곱 수로 만든 후에 각각의 CCTV 방향에 따라서 조사를 하기 위해서 4진법으로 변환해주면 된다.

for (int i = 0; i < tot; i++) {
    int temp = tot;

    for (int j = 0; j < size(cctv); j++) {
        int dir = temp % 4;
        temp /= 4;

4로 나눈 나머지 값이 dir이 되는 것이다. 나올 수 있는 dir 값은 0, 1, 2, 3으로 네가지 방향을 고려한다.

동서남북 4가지와 매칭된다.

 

 

(2) 사각지대를 어떻게 처리할 것인가?

CCTV의 좌표와 동서남북에 해당하는 방향을 파라미터로 전달하는 함수를 만든다.

void upd(int x, int y, int dir) {
	int X = x + dx[dir];
	int Y = y + dy[dir];

	while (true) {
		if (X < 0 || Y < 0 || X > n || Y > m || board2[X][Y] == 6) return;
		if (board2[X][Y] != 0) continue;
		board2[X][Y] = 7;
	}
}

board 경계를 넘어가거나 ( X < 0 || Y < 0 || X > n || Y > m ) 벽을 만났을 때 ( board2[X][Y] == 6 ) 함수 return을 한다.

그리고 board 값이 0이 아닌 경우 즉, CCTV이거나 (1 ~ 5) 이미 감시 구역으로 표시한 경우 (7) 같은 방향의 다음 칸을 조사하기 위해서 continue 해준다.

감시 구역인 경우에는 7로 표시한다.

 

 

(3) CCTV 별로 방향을 어떻게 처리할 것인가?

1번 CCTV는 한 경우 당 하나의 방향이므로 문제가 없다.

하지만 2번 ~ 5번 CCTV는 한 경우 당 2개 이상의 방향이므로 함수를 여러번 호출해주어야 한다.

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

 

 

(4) 최소 사각지대의 개수를 어떻게 파악할 것인가?

전체 tot 경우의 수 중에서 한 경우씩 사각지대의 최소 개수를 구해서 최솟값을 갱신해야 한다.

/* 처음에 입력 받을 때 */
for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
        cin >> board1[i][j];

        if (board1[i][j] != 0 && board1[i][j] != 6) cctv.push_back({ i, j });
        if (board1[i][j] == 0) blind_spot++;
    }
}

/* 사각지대 최솟값 구하기 */
int val = 0;
for (int a = 0; a < n; a++) {
    for (int b = 0; b < m; b++) {
        if (board2[a][b] == 0) val++;
    }
}
blind_spot = min(val, blind_spot);

처음 입력 받을 때 0인 경우 blind_spot을 1씩 증가해주었는데, 그 이유는 minimum 초기값의 상한선을 정해주기 위해서이다. min 함수를 쓰려고 하는데 무작정 큰 값 (예를 들면 inf)을 쓰는 것보다 아무래도 사각지대의 개수는 최대 0인 곳보다는 적을 것이기 때문에 이를 상한선으로 사용하는 것이 더 낫기 때문이다.

 

 

 

2. 전체 코드

# include <bits/stdc++.h>
using namespace std;
# define X first
# define Y second

int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };
int n, m;
int board1[10][10]; // 최초에 입력받은 board 저장
int board2[10][10]; // 사각지대 개수 세기 위한 board 저장
vector<pair<int, int>> cctv; // cctv 좌표를 저장할 변수

void upd(int x, int y, int dir) {
	dir %= 4;
	while (1) {
		x += dx[dir];
		y += dy[dir];

		if (x < 0 || x >= n || y < 0 || y >= m || board2[x][y] == 6) return;
		if (board2[x][y] != 0) continue;
		board2[x][y] = 7;
	}

}
int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	int blind_spot = 0;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> board1[i][j];

			if (board1[i][j] != 0 && board1[i][j] != 6) cctv.push_back({ i, j });
			if (board1[i][j] == 0) blind_spot++;
		}
	}

	long long tot = 1;
	for (int i = 0; i < cctv.size(); i++) tot *= 4;

	for (int tmp = 0; tmp < tot; tmp++) {
		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++)
				board2[i][j] = board1[i][j];

		// 10진법을 4진법으로 바꾸기 (tmp : cctv가 가리킬 수 있는 방향 조합 개수)
		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]; // x = cctv[i].X; y = cctv[i].Y; (CCTV 좌표 저장)

			if (board1[x][y] == 1) {
				upd(x, y, dir);
			}
			else if (board1[x][y] == 2) {
				upd(x, y, dir);
				upd(x, y, dir + 2);
			}
			else if (board1[x][y] == 3) {
				upd(x, y, dir);
				upd(x, y, dir + 1);
			}
			else if (board1[x][y] == 4) {
				upd(x, y, dir);
				upd(x, y, dir + 1);
				upd(x, y, dir + 2);
			}
			else if (board1[x][y] == 5) {
				upd(x, y, dir);
				upd(x, y, dir + 1);
				upd(x, y, dir + 2);
				upd(x, y, dir + 3);
			}
		}
		int val = 0;
		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++)
				val += (board2[i][j] == 0);
		blind_spot = min(blind_spot, val);
	}
	cout << blind_spot;
}