[ 삼성 SW역량 평가 15683 ] 감시 (C++)

[ 난이도 ]

★★☆

 

[ 문제 링크 ]

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

 

[ 문제 풀이 ]

해당 문제를 풀기위해

1. Vector를 사용하여 CCTV의 종류와 좌표를 저장하였다.

2. DFS를 재귀로 구현하여 모든 해당 CCTV의 모든 경우를 완벽탐색 하였다.

 

그림1

3. 해당 경우의 감시를 할경우 맵상에 9로 표시하였으며 6은 벽 1~5는 CCTV 인것을 고려하여 0인 것을 카운트 해준다.

 

[ 소스 코드 ]

// 헤더파일을 불러옵니다.
#include <iostream>
#include <vector>
using namespace std; 
// 맵의 최대 사이즈를 정의 합니다.
#define Map_Size 9
// 맵을 선언합니다.
int Map[Map_Size][Map_Size];
// CCTV의 종류와 좌표를 담을 벡터를 선언합니다.
vector<pair<int, pair<int, int>>> CCTV;
// N : 세로 길이, M : 가로 길이
int N, M;
// ans의 초기값
int ans = 987654321;
// 입력을 받아옵니다.
void Load_Input()
{
    cin >> N >> M;
    for (int i = 1; i <= N; ++i)
    {
        for (int j = 1; j <= M; ++j)
        {
            cin >> Map[i][j];
            // 만약 1~5사이의 CCTV라면 종류를 저장하고 좌표를 저장합니다.
            if (0 < Map[i][j] && Map[i][j] < 6)
            {
                CCTV.push_back(make_pair(Map[i][j], make_pair(i, j)));
            }
        }
    }
}
// 방향을 정해주고 CCTV좌표를 주면 해당 방향을 감시하는 함수입니다.
void Inspect(int dir,int x, int y)
{
    // ↑ 방향
    if (dir ==0)
    {
        int nx = x - 1;
        int    ny = y;
        if (nx <1 || nx > N || ny <1 || ny > M) return;
        if (Map[nx][ny] == 6) return;
        Map[nx][ny] = 9;
        Inspect(1, nx, ny);
    }
    // → 방향
    if (dir == 1)
    {
        int nx = x;
        int    ny = y + 1;
        if (nx <1 || nx > N || ny <1 || ny > M) return;
        if (Map[nx][ny] == 6) return;
        Map[nx][ny] = 9;
        Inspect(2, nx, ny);
    }
    // ↓ 방향
    if (dir == 2)
    {
        int nx = x + 1;
        int    ny = y;
        if (nx <1 || nx > N || ny <1 || ny > M) return;
        if (Map[nx][ny] == 6) return;
        Map[nx][ny] = 9;
        Inspect(3, nx, ny);
    }
    // ← 방향
    if (dir == 3)
    {
        int nx = x;
        int    ny = y - 1;
        if (nx <1 || nx > N || ny <1 || ny > M) return;
        if (Map[nx][ny] == 6) return;
        Map[nx][ny] = 9;
        Inspect(4, nx, ny);
    }
}
// 감시를 다했을경우 정답 ans를 갱신합니다.
void Check() {
    int cnt = 0;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            if (Map[i][j] == 0) {
                cnt += 1;
            }
        }
    }
    if (cnt < ans)
    {
        ans = cnt;
    }
}
// 맵을 복사하는 함수입니다.
void Copy_Map(int A[Map_Size][Map_Size], int B[Map_Size][Map_Size])
{
    for (int i = 1; i <= N; i++) 
    {
        for (int j = 1; j <= M; j++) 
        {
            A[i][j] = B[i][j];
        }
    }
}
// DFS로 모든 경우를 완전탐색 합니다.
void DFS(int cnt) // cnt는 CCTV의 종류입니다.
{
    // 모든 CCTV의 경우를 다 고려했을때 사각지대를 검색합니다
    if (cnt > (int)CCTV.size()-1)
    {
        Check();
        return;
    }
    // CCTV종류와 좌표를 받아옵니다.
    int Kind = CCTV.at(cnt).first;
    int x = CCTV.at(cnt).second.first;
    int y = CCTV.at(cnt).second.second;
    // 재귀를 할 경우 해당 맵을 기억하고 있어야 합니다.
    int CopyMap[Map_Size][Map_Size];
    if (Kind == 1)
    {
        for (int i = 0; i < 4; ++i)
        {
            Copy_Map(CopyMap,Map);
            Inspect(i, x, y);
            DFS(cnt + 1);
            Copy_Map(Map, CopyMap);
        }
    }
    if (Kind == 2)
    {
        for (int i = 0; i <= 1; ++i)
        {
            Copy_Map(CopyMap, Map);
            Inspect(i, x, y);
            Inspect(i + 2, x, y);
            DFS(cnt + 1);
            Copy_Map(Map, CopyMap);
        }
    }
    if (Kind == 3)
    {
        for (int i = 0; i < 4; ++i)
        {
            Copy_Map(CopyMap, Map);
            Inspect(i, x, y);
            Inspect((i + 1)%4, x, y);
            DFS(cnt + 1);
            Copy_Map(Map, CopyMap);
        }
    }
    if (Kind == 4)
    {
        for (int i = 0; i < 4; ++i)
        {
            Copy_Map(CopyMap, Map);
            Inspect(i, x, y);
            Inspect((i + 1) % 4, x, y);
            Inspect((i + 2) % 4, x, y);
            DFS(cnt + 1);
            Copy_Map(Map, CopyMap);
        }
    }
    if (Kind == 5)
    {
        Copy_Map(CopyMap, Map);
        Inspect(0, x, y);
        Inspect(1, x, y);
        Inspect(2, x, y);
        Inspect(3, x, y);
        DFS(cnt + 1);
        Copy_Map(Map, CopyMap);
    }
}
int main()
{
    Load_Input();
    DFS(0);
    cout << ans << endl;
    return 0;
}