[BOJ, C++]#15683_감시, 미로 유형 문제, 백트래킹, DFS

#1. 문제

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

 

---

 

#2. 풀이

 

1. 백트래킹

[알고리즘]#6_백트래킹

백트래킹은 문제의 여러 후보 해결책들을 점진적으로 탐색하며, 현재 선택한 경로가 해결책으로 이어질 수 없다고 판단되면, 이전 단계로 돌아가 다른 후보 경로에 대한 탐색을 시도하는 방법입니다. 일반적으로, 재귀 DFS를 활용하여 구현됩니다.

 

2. DFS

[자료구조]#6_그래프

DFS는 그래프의 모든 정점을 탐색하는 방법 중 하나로, 출발 정점으로부터 더 이상 확장 불가능한 단말 노드에 이르기까지  깊이 우선적으로 탐색하는 방법입니다. 일반적으로, DFS는 재귀 호출 혹은 스택 자료구조를 통해 구현합니다.

 

3. cctv 타입 별 방향 조합의 수를 찾고, 모든 cctv에 대하여 백트래킹 진행 

1. 먼저, 현재 단계에서 알아볼 cctv의 타입을 저장하고, 백트래킹을 수행합니다.
2. 모든 cctv의 타입 정보를 설정했다면, nxm 배열에 감시 가능한 구역을 체크하고, 사각지대의 개수를 계산합니다. 그리고, 최소 사각지대 값을 업데이트해줍니다.

 

---

 

#3. 코드

/*
    @링크: https://www.acmicpc.net/problem/15683
*   @문제: 주어진 NxM 크기의 미로에서 CCTV로 감시할 수 없는 사각지대의 최소 크기
*   @설명
        1. 백트래킹 활용
        2. cctv 위치 정보를 저장하고, 각 cctv 타입 별 방향 조합의 수(directionCounts)를 설정
        3. 현재 idx 정보와 direction 정보(dy와 dx의 인덱스 0~3중 하나)를 인자로 전달 받는 dfs 구현
        4. cctv 타입에 따른 방향 조합
            1. 현재 idx에 대응되는 cctv의 타입이 1이라면, dy[0]+dx[0] ~ dy[3]+dx[3] 까지 총 4개의 조합이 있습니다.
            2. 현재 idx에 대응되는 cctv의 타입이 2라면, (dy[0]+dx[0], dy[0+2]+dx[0+2]) + (dy[1]+dx[1], dy[1+2]+dx[1+2]) 총 2개의 조합이 있습니다.
            ...
        5. 모든 cctv에 대하여 방향 조합 정보를 모두 갖췄으면, 전체 배열을 임시로 저장해두고 0의 갯수를 세주어 사각지역의 최소 값을 업데이트 해줍니다.
*/


#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

#define MAX 8

typedef pair<int,int> p;

int N, M, cctvCnt, ans = 1e9;
int office[MAX][MAX];
int temp[MAX][MAX];
vector<p> cctvs;
vector<int> directions;

//@시계 방향
int dy[] = {-1, 0, 1, 0};
int dx[] = {0, 1, 0, -1};

//@CCTV 방향 개수
constexpr int directionCounts[] = {0, 4, 2, 4, 4, 1};

//@CCTV가 감시하는 방향
void watch(int y, int x, int dir) {
    dir %= 4;
    while (true) {
        y += dy[dir];
        x += dx[dir];
        if (y < 0 || x < 0 || y >= N || x >= M || temp[y][x] == 6) return;
        if (temp[y][x] != 0) continue;
        temp[y][x] = -1;  //@감시 영역 표시
    }
}

//@CCTV 감시 영역 설정
void setCCTV(int index, int dir) {
    int y = cctvs[index].first;
    int x = cctvs[index].second;
    int type = office[y][x];

    if (type == 1) {
        watch(y, x, dir);
    } else if (type == 2) {
        watch(y, x, dir);
        watch(y, x, dir+2);
    } else if (type == 3) {
        watch(y, x, dir);
        watch(y, x, dir+1);
    } else if (type == 4) {
        watch(y, x, dir);
        watch(y, x, dir+1);
        watch(y, x, dir+2);
    } else if (type == 5) {
        watch(y, x, dir);
        watch(y, x, dir+1);
        watch(y, x, dir+2);
        watch(y, x, dir+3);
    }
}

//@백트래킹
void dfs(int idx)
{
    //@종료 조건
    if(idx == cctvs.size())
    {
        //@임시 배열에 현재 상태 복사
        for(int i = 0; i < N; i++)
            for(int j = 0; j < M; j++)
                temp[i][j] = office[i][j];

        //@모든 CCTV 감시 영역 설정
        for(int i = 0; i < cctvs.size(); i++)
            setCCTV(i, directions[i]);

        //@사각지대(0의 갯수) 세기
        int unseen = 0;
        for(int i = 0; i < N; i++)
            for(int j = 0; j < M; j++)
                if(temp[i][j] == 0)
                    unseen++;

        //@최소값 갱신
        ans = min(ans, unseen);
        return;
    }

    //@현재 CCTV의 타입
    int type = office[cctvs[idx].first][cctvs[idx].second];

    //@가능한 모든 방향에 대해 재귀 호출
    for(int dir = 0; dir < directionCounts[type]; dir++) {
        directions.push_back(dir);
        dfs(idx + 1);
        directions.pop_back();
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    //@입력
    cin >> N >> M;

    //@사무실 상태 입력 및 CCTV 위치 저장
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            cin >> office[i][j];
            if(office[i][j] >= 1 && office[i][j] <= 5)
                cctvs.push_back({i,j});
        }
    }

    //@백트래킹 수행
    dfs(0);

    //@결과 출력
    cout << ans << '\n';

    return 0;
}

 

---