문제 링크 : https://www.acmicpc.net/problem/15683
반례 모음 : https://www.acmicpc.net/board/view/26220
5가지 종류의 cctv가 주어지고, 사무실 정보가 주어졌을 때 사각지대의 최소 크기를 구하는 문제이다.
<틀린 방법>
처음에는 한 cctv마다 4방향으로 볼 수 있는 좌표를 구해서 저장을 하고, cctv 번호에 따라서 최대로 볼 수 있는 개수가 있는 방향으로 감시를 하도록 했다.
설명을 되게 못썼는데, 예시로 설명을 해 보겠다.
1번 카메라 : 값 = 1, 방향별 감시할 수 있는 공간의 수 = 0 1 2 3 (상 하 좌 우 순서로 했다.)
2번 카메라 : 값 = 4, 방향별 감시할 수 있는 공간의 수 = 2 3 0 1
이렇게 두 개의 cctv가 있다고 할 때, 1번 카메라는 값이 1이므로 한 방향만 볼 수 있으므로 가장 많은 공간을 감시할 수 있는 오른쪽으로 고개를 틀어 3개의 공간을 감시하도록 설정한다.
2번 카메라는 값이 4이므로 총 3방향을 볼 수 있으므로 0개의 공간을 감시하는 왼쪽을 제외한 나머지 3방향을 감시하도록 설정했다.
항상 최대로 감시하는 경우로 세팅을 해서 코드를 작성하고 문제에서 주어진 테스트케이스는 전부 통과하여 제출을 했으나 바로 '틀렸습니다'가 떴다. 그리디한 방법인 것 같은데, 완전 탐색 문제라 통하지 않았나보다.
<맞은 방법>
구글링을 해서 코드는 참고하지 않고, 모든 카메라의 모든 방향을 체크해서 모든 경우의 수를 전부 순회한 뒤, 그 중 최소 크기의 사각지대를 구하도록 다시 코드를 짰다.
각 cctv마다 4방향으로 볼 수 있는 좌표를 구하는 것은 동일하되 그 이후에 cctv의 값에 따라 보는 방향을 백트래킹으로 전부 다 보도록 처리했더니 정답 처리되었다. 즉, 이전에는 내가 생각했을 때 최적의 경우만 체크를 했다면 완전 탐색으로 전부 다 순회하니 맞을 수 있었다.
예시로 설명하면,
1번 카메라가 '동쪽'을 보게 세팅, 2번 카메라가 '동서남'을 보게 세팅 -> 이때 사각지대 수 체크
1번 카메라는 그대로, 2번 카메라가 '동서북'을 보게 세팅 -> 사각지대 수
1번 카메라는 그대로, 2번 카메라가 '동남북'을 보게 세팅 -> 사각지대 수
1번 카메라는 그대로, 2번 카메라가 '서남북'을 보게 세팅 -> 사각지대 수
1번 카메라가 '서쪽'을 보게 세팅, 2번 카메라가 '동서남'을 보게 세팅 -> 사각지대 수
...
등으로 모든 경우의 수를 순회할 수 있도록 했다.
참고로 cctv의 숫자에 따라서
1 : ←, ↑, →, ↓ 4가지
2 : ←→, ↑↓ 2가지
3 : ←↑, ←↓, →↑, →↓ 4가지
4 : ←↑→, ↑→↓, →↓←, ←↓↑ 4가지
5 : ←↑→↓ 1가지
이렇게 경우의 수가 있다. 전부 코드로 처리해주면 된다!
<작성한 코드>
#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
#define min(a, b) (a < b ? a : b)
using namespace std;
int n, m, result = 100;
int board[9][9];
int dx[4] = {-1, 1, 0, 0}; // 상 하 좌 우
int dy[4] = {0, 0, -1, 1};
vector<pair<int, int>> v; // cctv 위치 저장
int blindSpot(){ // 사각지대
int cnt = 0;
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
if(board[i][j] == 0)
cnt++;
return cnt;
}
void changeBoard(queue<pair<int, int>> q, int val){
while(!q.empty()){
int x = q.front().first;
int y = q.front().second;
q.pop();
board[x][y] = val;
}
}
void dfs(int idx){
if(idx == v.size()){
result = min(result, blindSpot());
return ;
}
int x = v[idx].first;
int y = v[idx].second;
queue<pair<int, int>> q[4];
for(int i = 0; i < 4; i++){
int nx = x + dx[i];
int ny = y + dy[i];
while(0 <= nx && nx < n &&
0 <= ny && ny < m &&
board[nx][ny] != 6){
if(board[nx][ny] == 0)
q[i].push({nx, ny});
nx += dx[i];
ny += dy[i];
}
} // 4방향으로 볼 수 있는 모든 좌표 q에 저장
if(board[x][y] == 1){
for(int i = 0; i < 4; i++){
changeBoard(q[i], -1);
dfs(idx + 1);
changeBoard(q[i], 0);
}
}
else if(board[x][y] == 2){ // 수평, 수직 2방향
for(int i = 0; i < 3; i += 2){
changeBoard(q[i], -1);
changeBoard(q[i + 1], -1);
dfs(idx + 1);
changeBoard(q[i], 0);
changeBoard(q[i + 1], 0);
}
}
else if(board[x][y] == 3){ // 4가지
for(int i = 0; i < 2; i++){
changeBoard(q[i], -1);
for(int j = 2; j < 4; j++){
changeBoard(q[j], -1);
dfs(idx + 1);
changeBoard(q[j], 0);
}
changeBoard(q[i], 0);
}
}
else if(board[x][y] == 4){ // 3방향
for(int i = 0; i < 4; i++){
changeBoard(q[i], -1);
changeBoard(q[(i + 1) % 4], -1);
changeBoard(q[(i + 2) % 4], -1);
dfs(idx + 1);
changeBoard(q[i], 0);
changeBoard(q[(i + 1) % 4], 0);
changeBoard(q[(i + 2) % 4], 0);
}
}
else{
for(int i = 0; i < 4; i++)
changeBoard(q[i], -1);
dfs(idx + 1);
for(int i = 0; i < 4; i++)
changeBoard(q[i], 0);
}
}
int main(){
int cnt = 0;
cin >> n >> m;
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++){
cin >> board[i][j];
if(1 <= board[i][j] && board[i][j] <= 5)
v.push_back({i, j});
}
dfs(0);
cout << result;
}풀 때는 몰랐는데 알고보니 삼성 기출문제.. 역시 구현하기 너무 까다롭다. 생각만 좀 더 잘 하면 그래도 풀 수 있을지도.. 화이팅이다
