[BOJ] 백준 15683 감시 c++ (시뮬레이션, 구현) - 삼성 SW 역량 테스트 기출 문제

문제 출처 : https://www.acmicpc.net/problem/15683

15683번: 감시

 

---

풀이

방향에 따른 경우의 수를 모두 찾아 정답을 구하는 브루트포스 문제이다.

그러나 1,2,3,4,5번의 방향과 개수가 각각 달라 어떻게 시뮬레이션을 돌려야 할지 고민했다.

방향 시뮬레이션

우선 상하좌우 인덱스 dx, dy를 선언한다.

int dx[4] = {0, -1, 0, 1}; // 우, 상, 좌, 하
int dy[4] = {1, 0, -1, 0};

다음으로는 방향을 지정할 dir 매개변수를 선언해주고 dir에 따라 감시 영역을 탐색한다.

(dir이 1 증가할 수록 dx, dy 인덱스가 증가하므로 90도 회전한다)

void check(int x, int y, int dir){
    dir %= 4; // dir이 3보다 큰 경우를 위해
    while(1){
        int nx = x + dx[dir];
        int ny = y + dy[dir];
        x = nx;
        y = ny;
        if(nx < 0 || ny < 0 || nx >= N || ny >= M) return;
        if(arr[nx][ny] == 6) return;
        if(arr[nx][ny] != 0) continue;
        arr[nx][ny] = -1;
    }
}

시뮬레이션 함수에서는 1,2,3,4,5번에 따라 탐색할 방향을 모두 진행해주면 된다.

void dfs(int idx){
		...        
        if(arr[x][y] == 1)
            check(x, y, dir);
        else if(arr[x][y] == 2){
            check(x, y, dir);
            check(x, y, dir+2);
        }
        else if (arr[x][y] == 3){
            check(x, y, dir);
            check(x, y, dir + 1);
        }
        else if (arr[x][y] == 4){
            check(x, y, dir);
            check(x, y, dir + 1);
            check(x, y, dir + 2); 
        }
        else if (arr[x][y] == 5){
            check(x, y, dir);
            check(x, y, dir + 1);
            check(x, y, dir + 2);
            check(x, y, dir + 3);
        }
		...
}

---

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N, M;
int arr[8][8];
vector<pair<int, int>> cctv;
int ans = 987654321;

int dx[4] = {0, -1, 0, 1}; // 우, 상, 좌, 하
int dy[4] = {1, 0, -1, 0};

void check(int x, int y, int dir){
    dir %= 4;
    while(1){
        int nx = x + dx[dir];
        int ny = y + dy[dir];
        x = nx;
        y = ny;
        if(nx < 0 || ny < 0 || nx >= N || ny >= M) return;
        if(arr[nx][ny] == 6) return;
        if(arr[nx][ny] != 0) continue;
        arr[nx][ny] = -1;
    }
}

void dfs(int idx){
    if(idx == cctv.size()){
        int cnt = 0;
        for(int i = 0; i < N; i++)
            for(int j = 0; j < M; j++)
                if(!arr[i][j]) cnt++;

        ans = min(ans, cnt);
        return;
    }
    
    int x = cctv[idx].first;
    int y = cctv[idx].second;
    int tmp[9][9];

    for(int dir = 0; dir < 4; dir++){
        for(int i = 0; i < N; i++)
            for(int j = 0; j < M; j++)
                tmp[i][j] = arr[i][j];

        if(arr[x][y] == 1)
            check(x, y, dir);
        else if(arr[x][y] == 2){
            check(x, y, dir);
            check(x, y, dir+2);
        }
        else if (arr[x][y] == 3){
            check(x, y, dir);
            check(x, y, dir + 1);
        }
        else if (arr[x][y] == 4){
            check(x, y, dir);
            check(x, y, dir + 1);
            check(x, y, dir + 2); 
        }
        else if (arr[x][y] == 5){
            check(x, y, dir);
            check(x, y, dir + 1);
            check(x, y, dir + 2);
            check(x, y, dir + 3);
        }

        dfs(idx+1);
        // case 종료이므로 초기화
        for(int i = 0; i < N; i++)
            for(int j = 0; j < M; j++)
                arr[i][j] = tmp[i][j];
    }    
}

int main(){
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    cin >> N >> M;

    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            cin >> arr[i][j];
            if(arr[i][j] != 0 && arr[i][j] != 6)
                cctv.push_back({i, j});
        }
    }

    dfs(0);
    cout << ans << '\n';

    return 0;
}