[삼성SW테스트] 백준 15683번 - 감시 (정답률 39%)

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

15683번: 감시

삼성 SW테스트 기출문제다.

이 문제는 dfs탐색 + 시뮬레이션 유형의 문제로, 비트연산을 아주 유용하게 사용해 풀 수 있었다.

모든 cctv의 방향에 대해 사각지대를 계산해 최소값을 계산해야 하므로 비트 0부터 최대 수까지 올라가면서 각 cctv의 방향을 설정해주었다.

 

비트 설정은 아래와 같다.

00 -> 방향 0

01 -> 방향 1

02 -> 방향 2

03 -> 방향 3

 

방향이 총 동서남북 4방위이므로, 각 cctv당 방향은 2비트면 충분했다.

그리고 총 cctv의 개수는 최대 8개이므로, 16비트, 2바이트가 필요했다.

나는 int형 변수 bit를 for문안에 선언하고 1씩 증가시키며 cctv의 방향들에 대한 다음 조합을 구해나갔다.

 

다 푼뒤 제출했더니 틀렸다고 해서 비트가 잘못 들어가나 cout으로 찍어봤는데 이상하게 나와서 틀렸다. 이유를 확인해보니 비트 연산을 그냥 temp_bit >> 2 * i;로 해서 반영이 안되었던 거였다. -_-

당연히 temp_bit >>= 2*i;로 해야 비트가 오른쪽으로 이동하는 건데;; 참 어이없다.

+=, -=, *=, /=와 마찬가지로 >>=, <<= 하는 것을 까먹지 말자. 아참 &=도 된다. |=도 되겠지.

 

아무튼 비트 SHIFT, AND 연산을 이용해 풀 수 있었던 재미있는 브루트 포스 + dfs 탐색 문제였다.

 

아래는 소스코드 (20ms)

 

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#define maxlen 8
#define INF 987654321
using namespace std;
int map[maxlen][maxlen], temp_map[maxlen][maxlen];
bool visited[maxlen][maxlen];
int N, M;
int global_answer = INF;
 
vector<pair<pair<int, int>, pair<int, int> > > cctv;
typedef struct{
    int dr, dc;
}dir;
dir EW[2] = { { 0, 1 }, { 0, -1 } }; // 동서
dir SN[2] = { { 1, 0 }, { -1, 0 } }; // 남북
 
void reset(){
    for (int i = 0; i < N; i++){
        for (int j = 0; j < M; j++){
            temp_map[i][j] = map[i][j];
            visited[i][j] = false;
        }
    }
}
 
int counting(){
    // temp_map 사용할 것.
    int local_answer = 0;
    for (int i = 0; i < N; i++){
        for (int j = 0; j < M; j++){
            if (!visited[i][j] && temp_map[i][j] == 0){
                local_answer++;
                // 방문 안했고 0인 곳이 사각지역임. (cctv와 벽은 제외해야함.)
            }
 
        }
    }
    return local_answer;
}
 
void dfs_E(int r, int c){
    int n_r = r + EW[0].dr;
    int n_c = c + EW[0].dc;
    if (n_r >= 0 && n_r < N && n_c >= 0 && n_c < M){
        if (temp_map[n_r][n_c] >= 0 && temp_map[n_r][n_c] < 6){
            visited[n_r][n_c] = true;
            dfs_E(n_r, n_c);
        }
    }
}
 
void dfs_W(int r, int c){
    int n_r = r + EW[1].dr;
    int n_c = c + EW[1].dc;
    if (n_r >= 0 && n_r < N && n_c >= 0 && n_c < M){
        if (temp_map[n_r][n_c] >= 0 && temp_map[n_r][n_c] < 6){
            visited[n_r][n_c] = true;
            dfs_W(n_r, n_c);
        }
    }
}
 
void dfs_N(int r, int c){
    int n_r = r + SN[1].dr;
    int n_c = c + SN[1].dc;
    if (n_r >= 0 && n_r < N && n_c >= 0 && n_c < M){
        // 범위 내에 있고,
        if (temp_map[n_r][n_c] >= 0 && temp_map[n_r][n_c] < 6){
            visited[n_r][n_c] = true;
            dfs_N(n_r, n_c);
        }
    }
}
 
void dfs_S(int r, int c){
    int n_r = r + SN[0].dr;
    int n_c = c + SN[0].dc;
    if (n_r >= 0 && n_r < N && n_c >= 0 && n_c < M){
        // 범위 내에 있고,
        if (temp_map[n_r][n_c] >= 0 && temp_map[n_r][n_c] < 6){
            visited[n_r][n_c] = true;
            dfs_S(n_r, n_c);
        }
    }
}
 
void check(int th_cctv){
    int cur_row = cctv[th_cctv].first.first;
    int cur_col = cctv[th_cctv].first.second;
    int cur_type = cctv[th_cctv].second.first;
    int cur_direction = cctv[th_cctv].second.second;
    visited[cur_row][cur_col] = true;
    // temp_map 사용할 것.
    if (cur_type == 1){
        if (cur_direction == 0){
            dfs_N(cur_row, cur_col);
        }
        else if (cur_direction == 1)
            dfs_E(cur_row, cur_col);
        else if (cur_direction == 2)
            dfs_S(cur_row, cur_col);
        else if (cur_direction == 3)
            dfs_W(cur_row, cur_col);
    }
    if (cur_type == 2){
        if (cur_direction == 0 || cur_direction == 2){
            dfs_N(cur_row, cur_col);
            dfs_S(cur_row, cur_col);
        }
        else if (cur_direction == 1 || cur_direction == 3){
            dfs_E(cur_row, cur_col);
            dfs_W(cur_row, cur_col);
        }
    }
 
    if (cur_type == 3){
        if (cur_direction == 0){
            dfs_N(cur_row, cur_col);
            dfs_E(cur_row, cur_col);
        }
        else if (cur_direction == 1){
            dfs_E(cur_row, cur_col);
            dfs_S(cur_row, cur_col);
        }
        else if (cur_direction == 2){
            dfs_S(cur_row, cur_col);
            dfs_W(cur_row, cur_col);
        }
        else if (cur_direction == 3){
            dfs_W(cur_row, cur_col);
            dfs_N(cur_row, cur_col);
        }
    }
    if (cur_type == 4){
        if (cur_direction == 0){
            dfs_E(cur_row, cur_col);
            dfs_N(cur_row, cur_col);
            dfs_W(cur_row, cur_col);
        }
        else if (cur_direction == 1){
            dfs_N(cur_row, cur_col);
            dfs_S(cur_row, cur_col);
            dfs_E(cur_row, cur_col);
        }
        else if (cur_direction == 2){
            dfs_S(cur_row, cur_col);
            dfs_W(cur_row, cur_col);
            dfs_E(cur_row, cur_col);
        }
        else if (cur_direction == 3){
            dfs_N(cur_row, cur_col);
            dfs_W(cur_row, cur_col);
            dfs_S(cur_row, cur_col);
        }
    }
    if (cur_type == 5){
        dfs_E(cur_row, cur_col);
        dfs_W(cur_row, cur_col);
        dfs_N(cur_row, cur_col);
        dfs_S(cur_row, cur_col);
        // 전방위 탐색.
    }
 
}
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    cin >> N >> M;
    for (int i = 0; i < N; i++){
        for (int j = 0; j < M; j++){
            cin >> map[i][j];
            if (map[i][j] > 0 && map[i][j] < 6){
                //cctv
                cctv.push_back(make_pair(make_pair(i, j), make_pair(map[i][j], 0))); // ((행, 열), 종류). 종류: 1~5
            }
        }
    }
    reset();
    // map, temp_map, cctv, 방향 초기화 완료.
    // 방향은 0, 1, 2, 3이 존재하며, 순서대로 북/동/남/서. 
    // cctv가 1번일 경우 -> 각 방향 지향
    // cctv가 2번일 경우 -> 방향이 0/2면 남북
    //                     -> 방향이 1/3이면 동서
    // cctv가 3번일 경우 -> 각 방향 지향 (0,1,2,3 순서대로 북동/동남/남서/서북)
    // cctv가 4번일 경우 -> 각 방향 지향 (0,1,2,3 순서대로 북/동/남/서 제외)
    // cctv가 5번일 경우 -> 상관없이 모든 방향지향.
    int cctv_num = cctv.size(); // cctv개수.
    int target_bit = pow(2, 2 * cctv_num) - 1; // 0부터 1씩 더해가며 이 숫자까지 경우의 수 조사.
    for (int bit = 0; bit <= target_bit; bit++){
        // bit에 현재 경우의 수 (방향) 정보 저장.
        int temp_bit = bit;
        for (int i = 0; i < cctv_num; i++){
            temp_bit >>= 2 * i;
            temp_bit &= 3; // 11과 비트연산 and 하고
            cctv[i].second.second = temp_bit; // 방향 결과 넣어주면 됨.
            temp_bit = bit;
        }
 
        // dir_info에 각 cctv 방향 정보 저장됨.
        // 모든 cctv 확인.
        for (int i = 0; i < cctv.size(); i++){
            check(i);
        }
        int cur_ans = counting();
        global_answer = min(global_answer, cur_ans); // 정답 갱신.
        reset(); // temp_map 초기화, visited 초기화.
        //cout << bit << '\n';
        //for (int i = 0; i < cctv.size(); i++){
        //    cout << cctv[i].second.second << ' ';
        //}
        //cout << '\n';
    }
    cout << global_answer << '\n';
    //cout << pow(2, 0);
    //cout << target_bit << '\n';
    //cout << cctv_num;
    return 0;
}