[Algorithm] Baekjoon 15683번 : 감시

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

15683번: 감시

 
 
using namespace std;
 
struct Node
{
    int y;
    int x;
};
 
int n, m;
int arr[9][9] = { 0 };
vector<Node> camPositions;
 
vector<vector<vector<int>>> camDirs =
{
    {{0}},
    {{1},{2},{3},{0}},
    {{1,3},{0,2 }},
    {{0,1},{1,2},{2,3},{3,0} },
    {{3,0,1},{0,1,2}, {1,2,3},{2,3,0} },
    {{0,1,2,3}}
};
 
int dirs[4][2] = { {-1,0}, {0,1}, {1,0}, {0,-1} };
 
vector<int> curDirs;
int zeroCount = 0;
int answer = 0x3f3f3f3f;
 
 
void DFS(int index)
{
    if (index == camPositions.size())
    {
        bool visited[9][9] = { false };
        int tempCount = zeroCount;
 
        for (int i = 0; i < camPositions.size(); ++i)
        {
            int curY = camPositions[i].y;
            int curX = camPositions[i].x;
            int camNum = arr[curY][curX];
            visited[curY][curX] = true;
 
            for (int j = 0; j < camDirs[camNum][curDirs[i]].size(); ++j)
            {
                int curDir = camDirs[camNum][curDirs[i]][j];
                int nextY = curY + dirs[curDir][0];
                int nextX = curX + dirs[curDir][1];
 
                while (1)
                {
                    if (nextY < 0 || nextY == n) break;
                    if (nextX < 0 || nextX == m) break;
                    if (arr[nextY][nextX] == 6) break;
 
                    if (visited[nextY][nextX] == false)
                    {
                        if (arr[nextY][nextX] == 0)
                        {
                            --tempCount;
                            visited[nextY][nextX] = true;
                        }
                        else // 카메라면 걍 넘어가기
                        {
                            visited[nextY][nextX] = true;
                        }
                    }
 
                    nextY += dirs[curDir][0];
                    nextX += dirs[curDir][1];
                    
                }
            }
        }
 
        answer = min(answer, tempCount);
        return;
    }
 
    int camNum = arr[camPositions[index].y][camPositions[index].x];
    for (int i = 0; i < camDirs[camNum].size(); ++i)
    {
        curDirs.push_back(i);
        DFS(index + 1);
        curDirs.pop_back();
    }
}
 
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)
            {
                ++zeroCount;
            }
            else if (arr[i][j] >= 1 && arr[i][j] <= 5)
            {
                camPositions.push_back({ i,j });
            }
        }
    }
 
    DFS(0);
 
    cout << answer;
}

 

 

각 카메라타입에 따른 방향을 전부 룩업테이블에 정리해주고, 카메라회전에 대한 경우의수를 전부 DFS로 뽑아서 검사해주면 된다. 

모든 카메라가 4번회전하는게 아니라는걸 유의하자. 1번카메라는 한가지방향밖에 감시를 못해서 네방향에 대해 경우의 수를 뽑아야하지만, 2번카메라는 '한번에' 위아래, 혹은 좌우를 검사할 수 있기 때문에 인덱스계산에 안헷갈리도록 유의하자.