## [ Mine ]
[ Idea ]
-
1,2,3,4,5번 CCTV가 놓일 수 있는 방향은 각각 4가지, 2가지, 4가지, 4가지, 1가지 이다.
-
CCTV 종류별로 볼 수 있는 방향을 백트래킹으로 모두 찾는다.
-
해당 CCTV의 종류와 좌표 보고 있는 방향을 인자로 주면 board에 해당 영역을 색칠하는 함수를 구현한다.
-
이 2가지를 이용해서 각각의 케이스에 대해서 board를 색칠 한 후에 board에서 0의 갯수를 구한다.
-
각각의 경우에서 0의 최솟값을 구해서 출력한다.
[ Implementation ]
CCTV 종류별로 볼 수 있는 방향을 백트래킹으로 모두 찾는다.
int cctv_cnt = 0;
vector<pair<int, pair<int,int> > > cctv_infos;
int cases[5] = {4,2,4,4,1};
void back_track(int n){
if(n == cctv_cnt){
return_board();
for(int i = 0 ; i < arranged.size(); i++){
color(
cctv_infos[i].first,
arranged[i],
cctv_infos[i].second.first,
cctv_infos[i].second.second
);
}
ans = min(ans, get_zeros());
return;
}
int cctv_type = cctv_infos[n].first;
int dir_cases = cases[cctv_type - 1];
for(int i = 1; i <= dir_cases ; i++){
// 이 부분이 Point!! CCTV가 볼 수 있는 크기 만큼 상태 공간 트리를 만들어야 한다.
arranged.push_back(i);
back_track(n+1);
arranged.pop_back();
}
}해당 CCTV의 종류와 좌표 보고 있는 방향을 인자로 주면 board에 해당 영역을 색칠하는 함수를 구현한다.
void color_col_down(int r, int c);
void color_col_up(int r, int c);
void color_row_right(int r, int c);
void color_row_left(int r, int c);**
// 위의 4가지 함수는 r,c의 좌표를 입력받으면 해당 좌표의 하단, 상단, 우측, 좌측의 0을 7로 바꾼다.
// 이때, CCTV(1,2,3,4,5)는 넘기고 벽을 만나면 멈춘다.
// 당연히 board의 index의 범위를 넘어가면 멈춘다.
void color(int cctv_type, int dir_case, int r, int c){
switch(cctv_type){
case 1 : // type = 1;
switch( dir_case ){
case 1:
color_col_down(r,c);
break;
case 2:
color_col_up(r,c);
break;
case 3:
color_row_right(r,c);
break;
case 4:
color_row_left(r,c);
break;
}
break;
case 2 : // type = 2;
switch( dir_case ){
case 1:
color_col_down(r,c);
color_col_up(r,c);
break;
case 2:
color_row_left(r,c);
color_row_right(r,c);
break;
}
break;
case 3 : // type = 3;
switch( dir_case ){
case 1:
color_col_up(r,c);
color_row_right(r,c);
break;
case 2:
color_col_down(r,c);
color_row_right(r,c);
break;
case 3:
color_row_left(r,c);
color_col_down(r,c);
break;
case 4:
color_row_left(r,c);
color_col_up(r,c);
break;
}
break;
case 4 : // type = 4
switch( dir_case ){
case 1:
color_col_up(r,c);
color_row_right(r,c);
color_row_left(r,c);
break;
case 2:
color_col_down(r,c);
color_row_right(r,c);
color_row_left(r,c);
break;
case 3:
color_col_down(r,c);
color_col_up(r,c);
color_row_left(r,c);
break;
case 4:
color_col_down(r,c);
color_col_up(r,c);
color_row_right(r,c);
break;
}
break;
case 5 : // type = 5
switch( dir_case ){
case 1:
color_col_up(r,c);
color_col_down(r,c);
color_row_left(r,c);
color_row_right(r,c);
break;
}
break;
}
}
// 그리고 노가다로 각각의 케이스를 구분해서 board를 색칠하는 code를 만들었다...이 2가지를 이용해서 각각의 케이스에 대해서 board를 색칠 한 후에 board에서 0의 갯수를 구한다
if(n == cctv_cnt){
return_board();
for(int i = 0 ; i < arranged.size(); i++){
color(
cctv_infos[i].first,
arranged[i],
cctv_infos[i].second.first,
cctv_infos[i].second.second
);
}
ans = min(ans, get_zeros());
return;
}[ Bottleneck ]
-
일단 노가다 형식으로 코드를 작성해서 시간이 매우 오래 걸렸다.
-
백트래킹을 이용해서 구현하려다 보니 그 코드를 생각해내는것이 오래 걸렸다.
-
어떤 벡터나 배열은 인덱스를 1로 어떤건 0으로 되어있어서 인덱싱이 혼란스러웠다.
[ Kernel ]
-
구현 하는 시간은 오래걸렸지만 "내가 봤을 때" 코드가 매우 직관적이었고
-
함수로 분리가 되어 있어서 하나하나 검증하면서 넘어가기가 용이했다.
[ Full Code ]
#include <iostream>
#include <vector>
using namespace std;
void backtrack(int);
void color(int,int,int,int);
void print_board();
void return_board();
int get_zeros();
int cases[5] = {4,2,4,4,1};
vector<int> arranged;
int row;
int col;
int board[9][9];
int origin_board[9][9];
int cctv_cnt = 0;
vector<pair<int, pair<int,int> > > cctv_infos;
// [ CCTV 종류 , [ row 좌표, col 좌표 ]]
void return_board(){
for(int i = 0 ; i < row ; i++){
for(int j = 0 ; j < col ; j++){
board[i][j] = origin_board[i][j];
}
}
}
void get_input(){
cin >> row >> col;
for(int i = 0 ; i < row ; i++){
for(int j = 0 ; j < col ; j++){
int input;
cin >> input;
if(1 <= input && input <= 5){
cctv_cnt++;
pair<int, pair<int,int> > cctv_info = make_pair(input, make_pair(i,j));
cctv_infos.push_back(cctv_info);
}
origin_board[i][j] = input;
board[i][j] = input;
}
}
}
void init(){
ios::sync_with_stdio(0);
cin.tie(0);
}
void color_col_down(int r, int c){
// cout << "color_col_down!\n";
int n_row = r + 1;
while( n_row < row ){
if(1 <= board[n_row][c] && board[n_row][c] <= 5){
// CCTV는 pass
n_row++;
continue;
}
if(board[n_row][c] == 0 || board[n_row][c] == 7) {
// 벽이 아니면 -1로 색칠
board[n_row][c] = 7;
n_row++;
continue;
}
if(board[n_row][c] == 6){
return;
// 벽이면 return;
}
}
}
void color_col_up(int r, int c){
// cout << "color_col_up!\n";
int n_row = r - 1;
while( n_row >= 0 ){
if(1 <= board[n_row][c] && board[n_row][c] <= 5){
// CCTV는 pass
n_row--;
continue;
}
if(board[n_row][c] == 0 || board[n_row][c] == 7) {
// 벽이 아니면 -1로 색칠
board[n_row][c] = 7;
n_row--;
continue;
}
if(board[n_row][c] == 6){
return;
// 벽이면 return;
}
}
}
void color_row_right(int r, int c){
// cout << "color_row_right!\n";
int n_col = c + 1;
while( n_col < col ){
if(1 <= board[r][n_col] && board[r][n_col] <= 5){
// CCTV는 pass
n_col++;
continue;
}
if(board[r][n_col] == 0 || board[r][n_col] == 7) {
// 벽이 아니면 -1로 색칠
board[r][n_col] = 7;
n_col++;
continue;
}
if(board[r][n_col] == 6){
return;
// 벽이면 return;
}
}
}
void color_row_left(int r, int c){
// cout << "color_row_left!\n";
int n_col = c - 1;
while( n_col >= 0 ){
if(1 <= board[r][n_col] && board[r][n_col] <= 5){
// CCTV는 pass
n_col--;
continue;
}
if(board[r][n_col] == 0 || board[r][n_col] == 7) {
// 벽이 아니면 -1로 색칠
board[r][n_col] = 7;
n_col--;
continue;
}
if(board[r][n_col] == 6){
return;
// 벽이면 return;
}
}
}
int ans = 0x79999999;
void back_track(int n){
if(n == cctv_cnt){
return_board();
for(int i = 0 ; i < arranged.size(); i++){
// cout << arranged[i] << " ";
color(
cctv_infos[i].first,
arranged[i],
cctv_infos[i].second.first,
cctv_infos[i].second.second
);
}
// min(ans, get_zeros());
// print_board();
// cout << get_zeros() << "\n";
ans = min(ans, get_zeros());
return;
}
int cctv_type = cctv_infos[n].first;
//cctv_type = 1,2,3,4,5
int dir_cases = cases[cctv_type - 1];
// cases = 4,2,4,4,1
for(int i = 1; i <= dir_cases ; i++){
arranged.push_back(i);
back_track(n+1);
arranged.pop_back();
}
}
void color(int cctv_type, int dir_case, int r, int c){
switch(cctv_type){
case 1 : // type = 1;
switch( dir_case ){
case 1:
color_col_down(r,c);
break;
case 2:
color_col_up(r,c);
break;
case 3:
color_row_right(r,c);
break;
case 4:
color_row_left(r,c);
break;
}
break;
case 2 : // type = 2;
switch( dir_case ){
case 1:
color_col_down(r,c);
color_col_up(r,c);
break;
case 2:
color_row_left(r,c);
color_row_right(r,c);
break;
}
break;
case 3 : // type = 3;
switch( dir_case ){
case 1:
color_col_up(r,c);
color_row_right(r,c);
break;
case 2:
color_col_down(r,c);
color_row_right(r,c);
break;
case 3:
color_row_left(r,c);
color_col_down(r,c);
break;
case 4:
color_row_left(r,c);
color_col_up(r,c);
break;
}
break;
case 4 : // type = 4
switch( dir_case ){
case 1:
color_col_up(r,c);
color_row_right(r,c);
color_row_left(r,c);
break;
case 2:
color_col_down(r,c);
color_row_right(r,c);
color_row_left(r,c);
break;
case 3:
color_col_down(r,c);
color_col_up(r,c);
color_row_left(r,c);
break;
case 4:
color_col_down(r,c);
color_col_up(r,c);
color_row_right(r,c);
break;
}
break;
case 5 : // type = 5
switch( dir_case ){
case 1:
color_col_up(r,c);
color_col_down(r,c);
color_row_left(r,c);
color_row_right(r,c);
break;
}
break;
}
}
void print_board(){
cout << "\n";
for(int i = 0 ; i < row ; i++){
for(int j = 0 ; j < col ; j++){
cout << board[i][j] << " ";
}
cout << "\n";
}
cout << "\n";
}
int get_zeros(){
int cnt = 0;
for(int i = 0 ; i < row ; i++){
for(int j = 0 ; j < col ; j++){
if(board[i][j] == 0) cnt++;
}
}
return cnt;
}
int main(){
init();
get_input();
back_track(0);
cout << ans << "\n";
}[ Better One ]
[ Idea ]
-
중복 순열을 구현할 때에는 진법을 사용하면 편리하다!
-
방향에 따라 board를 탐색해야 하는 경우 진행 방향을 배열에 미리 설정해 놓자!
-
Modulo를 이용하자!
-
이렇게만 보면 이해가 잘 안갈 수 있다. 핵심 코드를 바로 보자!
[ Implementation ]
중복 순열을 구현할 때에는 진법을 사용하면 편리하다!
int cases = pow_4_n(N);
// n개중에서 r개를 나열하는 중복 순열을 모두 구하고자 한다면
// N을 R번 곱하고 그 수들을 나중에 R진법을 이용해서 다시 풀어주면 된다.
// 예를 들어 4개중에서 2개를 나열하는 중복 순열을 모두 구하고자 한다면.
// 0부터 15까지의 수 ( 16개 )를 각각 4진법을 사용하여 변환하면 된다.
for(int i = 0 ; i < cases; i++);{
vector<int> arrangement = get_cctv_arrangement(i, cctv_cnt);
}
vector<int> get_cctv_arrangement(int dec, int cctv_cnt){
vector<int> arrangement;
for(int i = 0 ; i < cctv_cnt; i++) {
arrangement.push_back(dec % 4);
dec /= 4;
}
return arrangement;
}
// 10진수로 받은 값을 4진수로 변환하여 뒤집은 값을 vector형태로 반환한다.
// ex) case = 4 일 때 // 반환 된 arrangement vector는 [0,1,0,0]이 되고
// ex) case = 9 일 때 // 반환 된 arrangement vector는 [0,0,2,1]이 된다.
// 각각의 숫자는 CCTV가 놓여진 방향과 대응된다.방향에 따라 board를 탐색해야 하는 경우 진행 방향을 배열에 미리 설정해 놓자!
int board[10][10];
const int d_row[4] = {0,1,0,-1};
const int d_col[4] = {1,0,-1,0};
// idx 0은 우측
// idx 1은 하단
// idx 2는 좌측
// idx 3은 상단
// 대각선으로 움직이는 것을 추가하고 싶다면
// d_row와 d_col에 그냥 해당 방향에 해당하는 값만 추가해주면 된다.
// 예를 들어 우측 상단으로 이동하고 싶다면
// d_row의 5번 idx에는 -1, d_col의 5번 idx에는 1을 추가해주면 된다.
void color(const int row, const int col, int dir){
const int dx = d_row[dir];
const int dy = d_col[dir];
// 입력된 방향에 따라 dx, dy만 갈아 끼워주면 된다.
int cur_row = row;
int cur_col = col;
while(1){
cur_row += dx; cur_col += dy;
if(cur_row < 0 || cur_row >= Row || cur_col < 0 || cur_col >= Col) return;
if(board[cur_row][cur_col] == 6) return;
if(board[cur_row][cur_col] >= 1 && board[cur_row][cur_col] <= 5) continue;
board[cur_row][cur_col] = 7;
}
return;
}**Modulo를 이용하자!
**void color_by_type(int row, int col ,int type, int dir){
switch (type)
{
case 1:
color(row, col, dir);
break;
case 2:
color(row, col, dir);
color(row, col, (dir + 2)%4);
// modulo의 성질을 이용하여 현재 방향과 180도 돌아간 방향
break;
case 3:
color(row, col, dir);
color(row, col, (dir + 1)%4);
// modulo의 성질을 이용해서 현재 방향과 90도 돌아간 방향
break;
case 4:
color(row, col, dir);
color(row, col, (dir + 1)%4);
color(row, col, (dir + 2)%4);
// modulo의 성질을 이용해서 현재 방향과 90, 180도 돌아간 방향
break;
case 5:
color(row, col, dir);
color(row, col, (dir + 1)%4);
color(row, col, (dir + 2)%4);
color(row, col, (dir + 3)%4);
// modulo의 성질을 이용해서
// 현재 방향과 90, 180, 270도 돌아간 방향을 모두 색칠 할 수 있다.
// 우아하다...
break;
}
}**[ Bottleneck ]
**color(row, col, (dir + 1));
color(row, col, (dir + 2));
color(row, col, (dir + 3));**-
위와 같이 modulo를 안쓰면 dir값으로 3이 입력되면 5,6이 들어 갈 수 있다.
-
위에서 사용한 방법들이 익숙하지 않아서 노가다를 뛰는 것보다 구현이 더 오래 걸렸다.
[ Kernel ]
-
중복 순열의 경우 개인적으로는 그냥 백트래킹을 써서 구현하는 것이 더 간편할 것 같다.
-
2차원 배열의 탐색을 할 때 탐색 가능한 방향을 미리 저장해두는 방식이 매우 좋은거 같다.
-
modulo의 특성을 이용하면 노가다성 문제도 쉽게 해결 할 수 있는것 같다. 매우 good이다!
[ Full code ]
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void print_copy_board();
void init(){
ios::sync_with_stdio(0);
cin.tie(0);
}
vector<int> Cctv_type;
vector<pair<int,int> > Cctv_loc;
int Row;
int Col;
int Board[10][10]; // original board
int Cctv_cnt = 0; // cctv 갯수
void get_input(){
cin >> Row >> Col;
for(int i = 0 ; i < Row; i++){
for(int j = 0 ; j < Col; j++){
int input;
cin >> input;
if( 1 <= input && input <= 5 ) {
Cctv_cnt++;
Cctv_type.push_back(input);
Cctv_loc.push_back(make_pair(i,j));
}
Board[i][j] = input;
}
}
}
int pow_4_n(int n){
int r_val = 1;
for(int i = 0; i < n; i++){
r_val *= 4;
}
return r_val;
}
vector<int> get_cctv_arrangement(int dec, int cctv_cnt){
vector<int> arrangement;
for(int i = 0 ; i < cctv_cnt; i++) {
arrangement.push_back(dec % 4);
dec /= 4;
}
return arrangement;
}
/*
0 : 동
1 : 남
2 : 서
3 : 북
*/
int board[10][10];
const int d_row[4] = {0,1,0,-1};
const int d_col[4] = {1,0,-1,0};
void color(const int row, const int col, int dir){
const int dx = d_row[dir]; // 1
const int dy = d_col[dir]; // 0
int cur_row = row;
int cur_col = col;
while(1){
cur_row += dx; cur_col += dy;
if(cur_row < 0 || cur_row >= Row || cur_col < 0 || cur_col >= Col) return;
if(board[cur_row][cur_col] == 6) return;
if(board[cur_row][cur_col] >= 1 && board[cur_row][cur_col] <= 5) continue;
board[cur_row][cur_col] = 7;
}
return;
}
void copy_board(){
for(int i = 0 ; i < Row; i++){
for(int j = 0; j < Col; j++){
board[i][j] = Board[i][j];
}
}
}
void color_by_type(int row, int col ,int type, int dir){
switch (type)
{
case 1:
color(row, col, dir);
break;
case 2:
color(row, col, dir);
color(row, col, (dir + 2)%4);
break;
case 3:
color(row, col, dir);
color(row, col, (dir + 1)%4);
break;
case 4:
color(row, col, dir);
color(row, col, (dir + 1)%4);
color(row, col, (dir + 2)%4);
break;
case 5:
color(row, col, dir);
color(row, col, (dir + 1)%4);
color(row, col, (dir + 2)%4);
color(row, col, (dir + 3)%4);
break;
}
}
int get_zeros(){
int cnt = 0;
for(int i = 0 ; i < Row; i++){
for(int j = 0; j < Col; j++){
cnt += (board[i][j] == 0);
}
}
return cnt;
}
int main(){
init();
get_input();
int cases = pow_4_n(Cctv_cnt);
int ans = 0x7FFFFFFF;
for(int i = 0 ; i < cases; i++){
vector<int> arrangement = get_cctv_arrangement(i, Cctv_cnt);
// ex) case = 4 일 때 // arrangement vector는 [0,1,0,0]이 되고
// ex) case = 9 일 때 // arrangement vector는 [0,0,2,1]이 된다.
// 각각의 숫자는 CCTV가 놓여진 방향과 대응된다.
copy_board();
//CCTV가 볼 수 있는 자리는 7로 마킹해야 하기 때문에 원본 Board를 따로 board에 복사해야 한다.
for(int j = 0 ; j < arrangement.size(); j++){
color_by_type(Cctv_loc[j].first, Cctv_loc[j].second, Cctv_type[j], arrangement[j]);
}
// 각각의 배열을 그린다.
int zeros = get_zeros();
if(zeros < ans){
ans = zeros;
}
}
cout << ans << "\n";
return 0;
}참조
위 설명에서 사용된 이미지와 설명의 일부는 바킹독님의 유트브와 바킹독님의 블로그의 강의내용과 강의 자료에서 발췌하였습니다.
