[백준] 감시 15683번 (c++) 구현, 배열 선언 위치의 중요성

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

풀이 방법

백트레킹을 이용한 브루트포스 문제이다.

 

사무실의 크기가 최대 8x8 이므로 브루트포스를 사용해서 성공할 수 있다.

cctv를 dfs로 돌아가며 하나씩 최대 4개의 방향을 돌아가며 다 검사하고 백트레킹을 통해 다시 돌아오는 삼성 기출문제의 연구실 문제와 유사하다. 

 

cctv의 타입에 따라 조사할 방향을 정해두면 된다. 

나는 아래와 같이 구현했다.

 

아래 코드에서 i는 for 문을 통해 0에서 3까지 반복 진행한다.

타입이 1인 경우 한쪽 방향만 볼 수 있다.

타입이 2인 경우 양 쪽 끝방향을 볼 수 있다.

타입이 3인 경우 직각인 방향을 볼 수 있다.

타입이 4인 경우 3가지 방향을 볼 수 있다.

타입이 5인 경우 4방향 다 볼 수 있다.

	if (cctv_type == 1) {
            check_area(y, x, i);
        }
        else if (cctv_type == 2) {
            check_area(y, x, i);
            check_area(y, x, i+2);
        }   
        else if (cctv_type == 3) {
            check_area(y, x, i);
            check_area(y, x, i+1);
        }

        else if (cctv_type == 4) {
            check_area(y, x, i);
            check_area(y, x, i+1);
            check_area(y, x, i+2);
        }

        else {
            check_area(y, x, i);
            check_area(y, x, i+1);
            check_area(y, x, i+2);
            check_area(y, x, i+3);
        }

실수한 부분

문제에서 핵심인 백트레킹을 구현하기 위해

cctv를 체크하기 전 상태를 저장 후 cctv가 볼 수 있는 부분을 office의 값 변경을 통해 수정 후 다음 인덱스의 cctv를 확인한 후 다시 돌아왔을 때 cctv를 체크하기 전 상태로 백업해주어야 한다. 이를 위해서는 체크하기 전 상태를 저장해야 하는데 체크하기 전 상태를 저장하기 위한 배열 선언을 글로벌하게 선언하게 된다면 온전하게 저장이 되지 못하면 값이 변경되게 된다. 그러므로 cctv를 통해 office 값을 변경해 주는 loop안에서 선언해주어야 한다.

 

전체 코드

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

using namespace std;


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


int dy[4] = {-1, 0, 1, 0}; // 북, 동, 남, 서
int dx[4] = {0, 1, 0, -1};

int count_area() { // cctv의 사각지대 체크하기
    int cnt = 0;
    for (int i = 0;i < N;i++) {
        for (int k = 0;k < M;k++) {
            if (office[i][k] == 0) { // 사각지대
                cnt++;
            }
        }
    }
    return cnt;
}

void check_area(int y, int x, int dir) {
    dir = dir % 4; // 4이상인거 인덱스 설정
    int ny = y;
    int nx = x;
    while(1) { // 벽이나 Office를 벗어날 때까지 수행
        ny += dy[dir];
        nx += dx[dir];

        if (ny < 0 || nx < 0 || ny >= N || nx >= M) return ; // 범위를 나가서 종료
        if (office[ny][nx] == 6) return ; // 벽이라서 종료
        if (office[ny][nx] != 0) continue; // 다른 cctv인 경우, 이미 체크되는 경우 계속 진행
        office[ny][nx] = -1;
    }
}

void dfs(int idx) { // cctv의 인덱스
    
    if (idx == cctv.size()) { // 모든 cctv확인 후 정답 체크        
        ans = min(ans, count_area());
        return;
    }

    int y = cctv[idx].first, x = cctv[idx].second;
    int cctv_type = office[y][x];
    for (int i = 0;i < 4;i++) {
        int temp[8][8]; // 실수한 부분 전역으로 선언하게 되면 값이 다르게 나온다.
        for (int j = 0;j < N;j++) { // 백트레킹을 위한 현재 office 상태 임시 저장
            for (int k = 0;k < M;k++) {
                temp[j][k] = office[j][k];
            }
        }

        if (cctv_type == 1) {
            check_area(y, x, i);
        }
        else if (cctv_type == 2) {
            check_area(y, x, i);
            check_area(y, x, i+2);
        }   
        else if (cctv_type == 3) {
            check_area(y, x, i);
            check_area(y, x, i+1);
        }

        else if (cctv_type == 4) {
            check_area(y, x, i);
            check_area(y, x, i+1);
            check_area(y, x, i+2);
        }

        else {
            check_area(y, x, i);
            check_area(y, x, i+1);
            check_area(y, x, i+2);
            check_area(y, x, i+3);
        }

        dfs(idx + 1); //다음 인덱스 수행

        for (int j = 0;j < N;j++) { //백트레킹 다시 원래로 수정
            for (int k = 0;k < M;k++) {
                office[j][k] = temp[j][k];
            }
        }
    }
    

}

int main() {

    cin >> N >> M;    
    for (int i =0;i < N;i++) {
        for (int k = 0;k < M;k++) {
            int a;
            cin >> a;
            if (1 <= a && a <= 5) { // cctv 위치 저장
                cctv.push_back(make_pair(i, k));
            }
            office[i][k] = a;
        }
    }    

    dfs(0);
    cout << ans << endl;
    return 0;
}