15683번: 감시
스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감시할 수 있는 방법은 다음과 같다. 1번 CCTV는 한 쪽 방향만 감시할 수 있다. 2번과 3번은 두 방향을 감시할 수 있는데, 2번은 감시하는 방향이 서로 반대방향이어야 하고, 3번은 직각 방향이어야 한다. 4번은 세 방향, 5번은 네 방향을 감시할
www.acmicpc.net
내공이 부족한 것을 다시한번 뼈저리게 느낀 문제..
알고리즘은 다음과 같다.
대각선으로는 감시를 못하기 때문에 어떤 cctv든 한쪽 방향에 대해서 y좌표만 1증감하거나, x좌표만 1증감한다.
따라서 코드의 중복을 막기 위해 가로방향과 세로방향에 대해 탐색하는 함수를 만들어 호출하도록 하였다.
1번 cctv는 상 하 좌 우 4개의 경우의 수, 2번 cctv는 상하 좌우 2개의 경우의 수,
3번 cctv는 상좌, 상우, 하좌, 하우 4개의 경우의 수, 4번 cctv는 상좌우 상하좌 상하우 하좌우 4개 경우의 수,
5번은 1개의 경우의 수가 존재하기 때문에 사무실에 존재하는 cctv들의 모든 경우의 수에 대하여 완전탐색하면 원하는 출력을 얻을 수 있다.
실력이 부족하여 코드가 조잡하기 때문에.. 이해하기 힘들 수도 있습니다.
|
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
const int INF = 987654321;
int maxCol, maxRow;
bool visited[8][8];
int result = INF;
vector<vector<int>> map;
int min(int a, int b) { return a < b ? a : b; }
void Solution(); // 전방선언
void ScanChange(int tempY, int tempX, int scanY, int scanX)
// CCTV가 볼 수 있는 0을 9로 바꿈
{
if(scanX == 0)
while (1)
{
tempY += scanY;
if (tempY >= maxCol || tempY < 0) break;
if (map[tempY][tempX] == 6) break;
if (map[tempY][tempX] == 0)
map[tempY][tempX] = 9;
}
else
while (1)
{
tempX += scanX;
if (tempX >= maxRow || tempX < 0) break;
if (map[tempY][tempX] == 6) break;
if (map[tempY][tempX] == 0)
map[tempY][tempX] = 9;
}
}
void GoScan(int y, int x, int type)
// CCTV 1번부터 5번까지 각각 다르게 동작
{
vector<vector<int>> temp(map);
int scan;
switch (type)
{
case 1:
scan = 1;
for (int i = 0; i < 2; i++)
{
ScanChange(y, x, 0, scan);
Solution();
map = temp;
ScanChange(y, x, scan, 0);
Solution();
map = temp;
scan = -1;
}
break;
case 2:
ScanChange(y, x, 0, 1);
ScanChange(y, x, 0, -1);
Solution();
map = temp;
ScanChange(y, x, 1, 0);
ScanChange(y, x, -1, 0);
Solution();
break;
case 3:
scan = 1;
for (int i = 0; i < 2; i++)
{
ScanChange(y, x, scan, 0);
ScanChange(y, x, 0, scan);
Solution();
map = temp;
ScanChange(y, x, scan, 0);
ScanChange(y, x, 0, scan*-1);
Solution();
map = temp;
scan = -1;
}
break;
case 4:
ScanChange(y, x, -1, 0);
ScanChange(y, x, 0, -1);
ScanChange(y, x, 0, 1);
Solution();
map = temp;
ScanChange(y, x, 0, 1);
ScanChange(y, x, 1, 0);
ScanChange(y, x, 0, -1);
Solution();
map = temp;
ScanChange(y, x, -1, 0);
ScanChange(y, x, 0, -1);
ScanChange(y, x, 1, 0);
Solution();
map = temp;
ScanChange(y, x, -1, 0);
ScanChange(y, x, 0, 1);
ScanChange(y, x, 1, 0);
Solution();
break;
case 5:
ScanChange(y, x, 0, 1);
ScanChange(y, x, 1, 0);
ScanChange(y, x, 0, -1);
ScanChange(y, x, -1, 0);
Solution();
break;
}
}
void Solution()
{
int yPos = -1, xPos = -1;
for (int i = 0; i < maxCol; i++)
{
for (int j = 0; j < maxRow; j++)
{
if (!visited[i][j] && map[i][j] != 0 && map[i][j] != 6 && map[i][j] != 9)
{
yPos = i;
xPos = j;
break;
}
if (yPos != -1) break; // 이중 for문 탈출
}
}
if (yPos == -1) // 기저사례. 모든 CCTV검사했을 시 사각지대 카운팅
{
int cnt = 0;
for (int i = 0; i < maxCol; i++)
for (int j = 0; j < maxRow; j++)
if (map[i][j] == 0) cnt++;
result = min(result, cnt);
return;
}
visited[yPos][xPos] = true;
GoScan(yPos, xPos, map[yPos][xPos]);
visited[yPos][xPos] = false;
}
int main(void)
{
cin >> maxCol >> maxRow;
vector<int> temp;
memset(visited, true, sizeof(visited));
for (int i = 0; i < maxCol; i++)
{
for (int j = 0; j < maxRow; j++)
{
int n;
cin >> n;
temp.push_back(n);
if (n != 0 && n != 6)
visited[i][j] = false;
}
map.push_back(temp);
temp.clear();
}
Solution();
cout << result << endl;
return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
|
알고리즘 200일 프로젝트 - 13day
내일도 열심히!
'알고리즘 > BOJ' 카테고리의 다른 글
| 백준 1748번: 수 이어 쓰기 1 (C++) (0) | 2020.04.20 |
|---|---|
| 백준 12100번: 2048(Easy) (C++) (0) | 2020.04.19 |
| 백준 1065번: 한수 (0) | 2020.04.17 |
| 백준 15686번: 치킨 배달 (C++) (0) | 2020.04.15 |
| 백준 14500번: 테트로미노 (C++) (0) | 2020.04.15 |