[골4] 15683 - 감시

https://github.com/encrypted-def/BOJ/blob/master/15683.cpp

 

아래는 내 코드다 cctv가 1일 때에 대비해서 풀지 못했다.

#include <iostream>
#include <vector>
#include <utility>

using namespace std;
using IntPair = pair<int, int>;
#define MAX_SIZE 100
#define y first
#define x second

int map[MAX_SIZE][MAX_SIZE]{ 0 };
int tmpMap[MAX_SIZE][MAX_SIZE]{ 0 };
int h, w;

// CCTV 위치 저장용도
vector<IntPair> vC;

// 다음 위치 시계 방향
IntPair pos[]
{
    { 1, 0 }, // 북
    { 0, 1 }, // 서
    {-1, 0 }, // 남
    { 0,-1 }  // 동
};

void DFS(int y, int x, int dir)
{
    while (true)
    {
        y += pos[dir].y;
        x += pos[dir].x;

        // 범위 체크
        if (y >= h ||
            y < 0 ||
            x >= w ||
            x < 0)
            return;

        auto val = map[y][x];
        if (val == 6)
            return;

        // 감시 가능한 영역임
        else if (val == 0)
                tmpMap[y][x] = 7;
    }
}

int main()
{
    cin >> h >> w;
    for (int y = 0; y < h; y++)
    {
    	for (int x = 0; x < w; x++)
        {
            cin >> map[y][x];
            auto val = map[y][x];

            // 빈 공간 또는 벽 제외
            if (val > 0 &&
                val < 6)
                vC.push_back({ y,x });
        }
    }
    int ans = 99;
    // 감시 영역을 찾음
    for (int i = 0; i < 4; i++)
    {
        memcpy(tmpMap, map, sizeof(map));
        for (auto cPos : vC)
        {
            // cctv 타입 분별
            int y = cPos.y, x = cPos.x;
            switch (map[y][x])
            {
            // 전 방향
            case 1: DFS(y, x, i); break;

            /* 두 방향
               좌 우 > 위 아래
               1,3 > 0,2 */
            case 2:
            {
                auto dir = (i + 1) % 2;
                DFS(y, x, dir);
                DFS(y, x, dir + 2);
            }
            break;

            /*  두 방향
                위 우 > 아래 우 > 아래 좌 > 위 좌
                0,3 > 2,3 > 2,1 > 0,1 */
            case 3:
            {
                IntPair tmpDir;

                switch (i)
                {
                case 0: tmpDir.y = 0, tmpDir.x = 3; break;
                case 1: tmpDir.y = 2, tmpDir.x = 3; break;
                case 2: tmpDir.y = 2, tmpDir.x = 1; break;
                case 3: tmpDir.y = 0, tmpDir.x = 1; break;
                }
                DFS(y, x, tmpDir.y);
                DFS(y, x, tmpDir.x);
            }
            break;

            /* 세 방향
                위 좌 우 > 위 우 아래 > 아래 좌 우 > 위 아래 좌
                0,1,3 > 0,3,2 > 2,1,3 > 0,2,1             
               */
            case 4:
            {
                int tmpX = 0, tmpY = 0, tmpZ = 0;
                switch (i)
                {
                case 0: tmpY = 1, tmpZ = 3; break;
                case 1: tmpY = 3, tmpZ = 2; break;
                case 3: tmpY = 2, tmpZ = 1; break;
                case 2: tmpX = 2, tmpY = 1, tmpZ = 3; break;
                }
                DFS(y, x, tmpX);
                DFS(y, x, tmpY);
                DFS(y, x, tmpZ);
            }
            break;

            // 전체방향
            case 5:
                DFS(y, x, 0);
                DFS(y, x, 1);
                DFS(y, x, 2); 
                DFS(y, x, 3);
                break;
            }
        }
        int tmp = 0;
        // 검사
        for (int y = 0; y < h; y++)
        {
            for (int x = 0; x < w; x++)
            {
                if (tmpMap[y][x] == 0)
                    tmp++;
            }
        }
        cout << tmp << endl;
        ans = min(ans, tmp);
    }
    
    //cout << ans;
}