[BOJ] 15683번 : 감시

1. problem : 

https://www.acmicpc.net/problem/15683

 

2. solution 1 :

#include <bits/stdc++.h>
using namespace std;
int office[8][8];
int minZero = 1000;
int N, M; // row , col; 
vector<tuple<int, int, int>> v_cctv; // cctv 위치와 종류저장

void xplus_count(int x, int y) {
	while (y < M-1) {
		y++;
		int idx_val = office[x][y]; //x축 양의방향으로 옮겼을 때 들어있는 값;
		if (idx_val == 0) office[x][y] = -1;
		else if (idx_val == 6) return;
		else if (idx_val == -1 || (idx_val > 0 && idx_val < 6)) continue; 
	}
}
void xminus_count(int x, int y) {
	while (y > 0) {
		y--;
		int idx_val = office[x][y]; //x축 음의방향으로 옮겼을 때 들어있는 값;
		if (idx_val == 0) office[x][y] = -1;
		else if (idx_val == 6) return;
		else if (idx_val == -1 || (idx_val > 0 && idx_val < 6)) continue;
	}
}
void yplus_count(int x, int y) {
	while (x < N-1) {
		x++;
		int idx_val = office[x][y]; //y축 양의방향으로 옮겼을 때 들어있는 값;
		if (idx_val == 0) office[x][y] = -1;
		else if (idx_val == 6) return;
		else if (idx_val == -1 || (idx_val > 0 && idx_val < 6)) continue;
	}
}
void yminus_count(int x, int y) {
	while (x > 0) {
		x--;
		int idx_val = office[x][y]; //y축 음의방향으로 옮겼을 때 들어있는 값;
		if (idx_val == 0) office[x][y] = -1;
		else if (idx_val == 6) return;
		else if (idx_val == -1 || (idx_val > 0 && idx_val < 6)) continue;
	}
}

void backTrack(int k) {//param은 감시카메라의 갯수;
	if (k == v_cctv.size()) {
		int zeroCount = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (office[i][j] == 0) zeroCount++;
			}
		}
		minZero = min(minZero, zeroCount);
		return;
	}
	int x = get<0>(v_cctv[k]);
	int y = get<1>(v_cctv[k]);
	int type = get<2>(v_cctv[k]); 

	// backTrack 후 복구코드 
	int backup[8][8];
	memcpy(backup, office, sizeof(office));
	if (type == 1) {
		xplus_count(x, y);
		backTrack(k + 1);
		memcpy(office, backup, sizeof(office));
		
		xminus_count(x, y);
		backTrack(k + 1);
		memcpy(office, backup, sizeof(office));

		yplus_count(x, y);
		backTrack(k + 1);
		memcpy(office, backup, sizeof(office));

		yminus_count(x, y);
		backTrack(k + 1);
		memcpy(office, backup, sizeof(office));
	}
	else if (type == 2) {
		xplus_count(x, y);
		xminus_count(x, y);
		backTrack(k + 1); 
		memcpy(office, backup, sizeof(office));

		yplus_count(x, y);
		yminus_count(x, y);
		backTrack(k + 1);
		memcpy(office, backup, sizeof(office));
	}
	else if (type == 3) {
		xplus_count(x, y);
		yplus_count(x, y);
		backTrack(k + 1);
		memcpy(office, backup, sizeof(office));

		yplus_count(x, y);
		xminus_count(x, y);
		backTrack(k + 1);
		memcpy(office, backup, sizeof(office));

		xminus_count(x, y);
		yminus_count(x, y);
		backTrack(k + 1);
		memcpy(office, backup, sizeof(office));

		yminus_count(x, y);
		xplus_count(x, y);
		backTrack(k + 1);
		memcpy(office, backup, sizeof(office));
	}
	else if (type == 4) {
		xplus_count(x, y);
		yplus_count(x, y);
		xminus_count(x, y);
		backTrack(k + 1);
		memcpy(office, backup, sizeof(office));

		yplus_count(x, y);
		xminus_count(x, y);
		yminus_count(x, y);
		backTrack(k + 1);
		memcpy(office, backup, sizeof(office));

		xminus_count(x, y);
		yminus_count(x, y);
		xplus_count(x, y);
		backTrack(k + 1);
		memcpy(office, backup, sizeof(office));

		yminus_count(x, y);
		xplus_count(x, y);
		yplus_count(x, y);
		backTrack(k + 1);
		memcpy(office, backup, sizeof(office));
	}
	else if (type == 5) {
		xplus_count(x, y);
		yplus_count(x, y);
		xminus_count(x, y);
		yminus_count(x, y);
		backTrack(k + 1);
	}

}						
	

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N >> M;
	
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> office[i][j];
			if (office[i][j] != 0 && office[i][j] != 6) v_cctv.push_back({ i,j,office[i][j] }); // 감시카메라 위치, 감시카메라 종류 저장
		}
	}
	backTrack(0);
	cout << minZero << '\n';
}

뭔가 비효율적이다. 같은 코드를 더 줄일 수 있을 것 같은데.. 

 

 

3. solution 2 :

// Authored by : BaaaaaaaaaaarkingDog
// Co-authored by : -
// http://boj.kr/c961e6bf6107428caf200c11c964f9e1
#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]; // 사각 지대의 개수를 세기 위해 사용할 변수
vector<pair<int,int> > cctv; // cctv의 좌표를 저장할 변수

bool OOB(int a, int b){ // Out Of Bounds 확인
  return a < 0 || a >= n || b < 0 || b >= m;
}

// (x,y)에서 dir 방향으로 진행하면서 벽을 만날 때 까지 지나치는 모든 빈칸을 7로 바꿔버림
void upd(int x, int y, int dir){
  dir %= 4;
  while(1){
    x += dx[dir];
    y += dy[dir];
    if(OOB(x,y) || board2[x][y] == 6) return; // 범위를 벗어났거나 벽을 만나면 함수를 탈출
    if(board2[x][y] != 0) continue; // 해당 칸이 빈칸이 아닐 경우(=cctv가 있을 경우) 넘어감
    board2[x][y] = 7; // 빈칸을 7로 덮음
  }
}

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m;
  int mn = 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) mn++;
    }
  }
  // 1 << (2*cctv.size())는 4의 cctv.size()승을 의미.
  for(int tmp = 0; tmp < (1<<(2*cctv.size())); tmp++){ // tmp를 4진법으로 뒀을 때 각 자리수를 cctv의 방향으로 생각할 것이다.
    for(int i = 0; i < n; i++)
      for(int j = 0; j < m; j++)
        board2[i][j] = board1[i][j];
    int brute = tmp;    
    for(int i = 0; i < cctv.size(); i++){
      int dir = brute % 4;
      brute /= 4;
      int x = cctv[i].X;
      int y = cctv[i].Y; // tie(x, y) = cctv[i];로 쓰면 1줄로 줄일 수 있음
      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{ // 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);
    mn = min(mn, val);
  }
  cout << mn;
}

source code 출처 : https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x0D/solutions/15683.cpp

basic-algo-lecture/0x0D/solutions/15683.cpp at master · encrypted-def/basic-algo-lecture