728x90
반응형
삼성 SW 기출 문제이며, 꽤나 긴 코드를 요구하는 문제이다.
dfs로 구현했다.
CCTV 종류는 총 5가지로, 다음과 같이 회전할 수 있다.
따라서 방향을 미리 설정해뒀다.
pair<int,int> direction[] = {{-1,0}, {1,0}, {0, -1}, {0, 1}};
pair<pair<int,int>,pair<int,int>> secondDirection[]
= {{{-1,0}, {1,0}},{{0,-1},{0,1}}};
pair<pair<int,int>,pair<int,int>> thirdDirection[]
= {{{-1,0},{0,-1}},{{1,0},{0,1}}, {{1,0},{0,-1}}, {{-1,0},{0,1}}};
tuple<pair<int,int>, pair<int,int>, pair<int,int>> fourthDirection[]
= {{{-1,0},{0,-1},{1,0}},{{0,-1},{-1,0},{0,1}},{{1,0},{-1,0},{0,1}},{{0,1},{0,-1},{1,0}}};
더 나은 방식이 있었을텐데 빨리 풀려고 하다보니 하드코딩이 됐다.
그후 dfs로 여러 방향을 비추는 CCTV 조합을 구한다.
void dfs(int index){
if(index == cctvVector.size()){
int answer = getCount();
minNum = min(minNum, answer);
return;
}
int copiedMatrix[8][8];
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
copiedMatrix[i][j] = matrix[i][j];
}
}
int cctvNum = cctvVector[index];
switch(cctvNum){
case 1:
for(int i = 0; i < 4; i++){
watchForFirstCCTV(index, i);
dfs(index + 1);
copyMap(copiedMatrix);
}
break;
case 2:
for(int i = 0; i < 2; i++){
watchForSecondCCTV(index, i);
dfs(index + 1);
copyMap(copiedMatrix);
}
break;
case 3:
for(int i = 0; i < 4; i++){
watchForThirdCCTV(index, i);
dfs(index + 1);
copyMap(copiedMatrix);
}
break;
case 4:
for(int i = 0; i < 4; i++){
watchForFourthCCTV(index, i);
dfs(index + 1);
copyMap(copiedMatrix);
}
break;
case 5:
watchForFifthCCTV(index);
dfs(index + 1);
break;
}
}
반복문을 돌렸을 때 copyMap을 해야하는데, 함수 호출을 완료 하고,
기존 함수에서 CCTV가 빈 곳(0)을 탐색하기 전 상태로 돌아가기 위한 작업이다.
참고로 탐색하기 전 상태로 돌아가는 것이니 글로벌 변수로 설정하게 되면
호출 완료하기 전 재귀에서 변경될 가능성이 있으므로
글로벌 변수로는 절대로 설정하면 안된다.
void copyMap(int copiedMatrix[8][8]){
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
matrix[i][j] = copiedMatrix[i][j];
}
}
}
이제 각 종류의 CCTV가 빈 곳을 어떤 방식으로 탐색하는지 살펴보자.
void watchCCTV(int dx,int dy, int directx, int directy){
while(1){
dx += directx;
dy += directy;
if(dx < 0 || dx >= n || dy < 0 || dy >= m || matrix[dx][dy] == 6) break;
if(matrix[dx][dy] == 0){
matrix[dx][dy] = 7;
}
}
}
우선 범위를 벗어나거나 벽(6)을 만나게 될 경우 CCTV가 닿지 않는 공간이므로 탐색을 종료한다.
위에서 언급했던 CCTV 방향을 연속적으로 더하고, 현 위치가 0일 경우
CCTV가 영향을 미치는 공간이므로, 공간의 값을 7로 설정한다.
위에서 언급했던 CCTV 방향은 이렇다.
pair<int,int> direction[] = {{-1,0}, {1,0}, {0, -1}, {0, 1}};
pair<pair<int,int>,pair<int,int>> secondDirection[]
= {{{-1,0}, {1,0}},{{0,-1},{0,1}}};
pair<pair<int,int>,pair<int,int>> thirdDirection[]
= {{{-1,0},{0,-1}},{{1,0},{0,1}}, {{1,0},{0,-1}}, {{-1,0},{0,1}}};
tuple<pair<int,int>, pair<int,int>, pair<int,int>> fourthDirection[]
= {{{-1,0},{0,-1},{1,0}},{{0,-1},{-1,0},{0,1}},{{1,0},{-1,0},{0,1}},{{0,1},{0,-1},{1,0}}};
그리고 각 CCTV 별 방향에 대한 탐색을 호출하는 함수를 구현했다.
void watchForFirstCCTV(int index, int directionIdx){
watchCCTV(cctvVertexVector[index].first,
cctvVertexVector[index].second,
direction[directionIdx].first,
direction[directionIdx].second);
}
void watchForSecondCCTV(int index, int directionIdx){
watchCCTV(cctvVertexVector[index].first,
cctvVertexVector[index].second,
secondDirection[directionIdx].first.first,
secondDirection[directionIdx].first.second);
watchCCTV(cctvVertexVector[index].first,
cctvVertexVector[index].second,
secondDirection[directionIdx].second.first,
secondDirection[directionIdx].second.second);
}
void watchForThirdCCTV(int index, int directionIdx){
watchCCTV(cctvVertexVector[index].first,
cctvVertexVector[index].second,
thirdDirection[directionIdx].first.first,
thirdDirection[directionIdx].first.second);
watchCCTV(cctvVertexVector[index].first,
cctvVertexVector[index].second,
thirdDirection[directionIdx].second.first,
thirdDirection[directionIdx].second.second);
}
void watchForFourthCCTV(int index, int directionIdx){
watchCCTV(cctvVertexVector[index].first,
cctvVertexVector[index].second,
get<0>(fourthDirection[directionIdx]).first,
get<0>(fourthDirection[directionIdx]).second);
watchCCTV(cctvVertexVector[index].first,
cctvVertexVector[index].second,
get<1>(fourthDirection[directionIdx]).first,
get<1>(fourthDirection[directionIdx]).second);
watchCCTV(cctvVertexVector[index].first,
cctvVertexVector[index].second,
get<2>(fourthDirection[directionIdx]).first,
get<2>(fourthDirection[directionIdx]).second);
}
하드코딩이 되어있기 때문에 좀 더 효율적인 방법을 찾았으면 좋을 거 같다.
작성한 코드는 이렇다.
//감시
#include <iostream>
#include <vector>
#include <tuple>
using namespace std;
pair<int,int> direction[] = {{-1,0}, {1,0}, {0, -1}, {0, 1}};
pair<pair<int,int>,pair<int,int>> secondDirection[]
= {{{-1,0}, {1,0}},{{0,-1},{0,1}}};
pair<pair<int,int>,pair<int,int>> thirdDirection[]
= {{{-1,0},{0,-1}},{{1,0},{0,1}}, {{1,0},{0,-1}}, {{-1,0},{0,1}}};
tuple<pair<int,int>, pair<int,int>, pair<int,int>> fourthDirection[]
= {{{-1,0},{0,-1},{1,0}},{{0,-1},{-1,0},{0,1}},{{1,0},{-1,0},{0,1}},{{0,1},{0,-1},{1,0}}};
int n,m, minNum = 987654321;
int matrix[8][8];
vector<int> cctvVector;
vector<pair<int,int>> cctvVertexVector;
void watchCCTV(int dx,int dy, int directx, int directy){
while(1){
dx += directx;
dy += directy;
if(dx < 0 || dx >= n || dy < 0 || dy >= m || matrix[dx][dy] == 6) break;
if(matrix[dx][dy] == 0){
matrix[dx][dy] = 7;
}
}
}
void copyMap(int copiedMatrix[8][8]){
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
matrix[i][j] = copiedMatrix[i][j];
}
}
}
void watchForFirstCCTV(int index, int directionIdx){
watchCCTV(cctvVertexVector[index].first,
cctvVertexVector[index].second,
direction[directionIdx].first,
direction[directionIdx].second);
}
void watchForSecondCCTV(int index, int directionIdx){
watchCCTV(cctvVertexVector[index].first,
cctvVertexVector[index].second,
secondDirection[directionIdx].first.first,
secondDirection[directionIdx].first.second);
watchCCTV(cctvVertexVector[index].first,
cctvVertexVector[index].second,
secondDirection[directionIdx].second.first,
secondDirection[directionIdx].second.second);
}
void watchForThirdCCTV(int index, int directionIdx){
watchCCTV(cctvVertexVector[index].first,
cctvVertexVector[index].second,
thirdDirection[directionIdx].first.first,
thirdDirection[directionIdx].first.second);
watchCCTV(cctvVertexVector[index].first,
cctvVertexVector[index].second,
thirdDirection[directionIdx].second.first,
thirdDirection[directionIdx].second.second);
}
void watchForFourthCCTV(int index, int directionIdx){
watchCCTV(cctvVertexVector[index].first,
cctvVertexVector[index].second,
get<0>(fourthDirection[directionIdx]).first,
get<0>(fourthDirection[directionIdx]).second);
watchCCTV(cctvVertexVector[index].first,
cctvVertexVector[index].second,
get<1>(fourthDirection[directionIdx]).first,
get<1>(fourthDirection[directionIdx]).second);
watchCCTV(cctvVertexVector[index].first,
cctvVertexVector[index].second,
get<2>(fourthDirection[directionIdx]).first,
get<2>(fourthDirection[directionIdx]).second);
}
}
int getCount(){
int count = 0;
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(matrix[i][j] == 0){
count++;
}
}
}
return count;
}
void dfs(int index){
if(index == cctvVector.size()){
int answer = getCount();
minNum = min(minNum, answer);
return;
}
int copiedMatrix[8][8];
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
copiedMatrix[i][j] = matrix[i][j];
}
}
int cctvNum = cctvVector[index];
switch(cctvNum){
case 1:
for(int i = 0; i < 4; i++){
watchForFirstCCTV(index, i);
dfs(index + 1);
copyMap(copiedMatrix);
}
break;
case 2:
for(int i = 0; i < 2; i++){
watchForSecondCCTV(index, i);
dfs(index + 1);
copyMap(copiedMatrix);
}
break;
case 3:
for(int i = 0; i < 4; i++){
watchForThirdCCTV(index, i);
dfs(index + 1);
copyMap(copiedMatrix);
}
break;
case 4:
for(int i = 0; i < 4; i++){
watchForFourthCCTV(index, i);
dfs(index + 1);
copyMap(copiedMatrix);
}
break;
case 5:
watchForFifthCCTV(index);
dfs(index + 1);
break;
}
}
int main(void){
cin >> n >> m;
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
cin >> matrix[i][j];
if(matrix[i][j] != 0 && matrix[i][j] != 6){
cctvVector.push_back(matrix[i][j]);
cctvVertexVector.push_back({i,j});
}
}
}
dfs(0);
cout << minNum;
}
반응형
'algorithm' 카테고리의 다른 글
[algorithm] 백준 - 드래곤 커브 (0) | 2020.12.27 |
---|---|
[algorithm] 백준 - 사다리 조작 (0) | 2020.12.25 |
[algorithm] 백준 - 톱니바퀴 (0) | 2020.12.24 |
[algorithm] 백준 - 연구소 (0) | 2020.12.24 |
[algorithm] 백준 - 경사로 (0) | 2020.12.23 |