백준 15683 감시

빡 구현 문제이다. 회전 얘기를 못 듣고 1번은 왼쪽만 볼 수 있고, 2번은 좌우만 볼 수 있고... 로 생각해서 다 구현하고 나니 잘못생각했더라... 문제에서 최소 크기 라는 단어가 있을때 뭔가 이상하네... 했는데 잘 생각했어야 했다...

 

회전의 경우를 생각해보면, 1번 3번 4번 카메라는 4개의 경우의 수가 있고, 2번 카메라는 2개, 5번 카메라는 1개의 경우의 수가 있다.

그 경우를 DFS로 탐색했다. 카메라가 k개 있다 하면, 탐색은 k 깊이로 이루어지고, 각 카메라가 몇번 카메라인지에 따라 해당 함수 호출에서 갈라지는 개수가 달라지도록 구성했다.

그것 외에는 구냥 구현이다. 진짜 딱 구현 문제라서 뭐라고 설명하기가 그렇다.

 

카메라가 보는 곳은 각 방향별로 인덱스를 줄이거나 늘려가면서 맵 범위 초과나 벽을 만날때까지 감시 범위를 표시했다.

depth를 확인해서 마지막 카메라까지 본 경우, 전체 맵을 탐색하면서 카메라 감시 범위가 아닌 곳을 리턴하도록 했다. 위 단계 호출에서는 각 경우마다 최소값을 받고 출력한다.

---

#include <iostream>
#include <vector>
#include <cstring>
#include <climits>

int n, m;
int map[10][10];

int dfs(int temp_i[10][10], int depth, std::vector<std::pair<int, int>> cameras)
{
    if (depth == cameras.size())
    {
        int sight = 0;
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                if (temp_i[i][j] == 0)
                    sight++;
            }
        }
        // std::cout <<"\n";
        //     for (int p_y = 0; p_y < n; p_y++)
        //     {
        //         for (int p_x = 0; p_x < m; p_x++)
        //             std::cout << temp_i[p_y][p_x] << " ";
        //         std::cout <<"\n";
        //     }
        //     std::cout << "\n------------------\n";
        return (sight);
    }
    else
    {
        int temp[10][10];
        int ret = INT_MAX;

        std::pair<int, int> camera = cameras[depth];
        int camtype = map[camera.first][camera.second];
        int maxrot;
        if (camtype == 1 || camtype == 3 || camtype == 4)
            maxrot = 4;
        else if (camtype == 2)
            maxrot = 2;
        else
            maxrot = 1;
        for (int camrot = 0; camrot < maxrot; camrot++)
        {
            for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
                temp[i][j] = temp_i[i][j];
        }
            if ((camtype == 1 && camrot == 0) ||
                (camtype == 2 && camrot == 0) ||
                (camtype == 3 && !(camrot % 2)) ||
                (camtype == 4 && camrot != 1) || camtype == 5) // ->
            {
                int y = camera.first;
                int x = camera.second;
                while (y < n)
                {
                    temp[y][x] = '#';
                    y++;
                    if (y == n || temp[y][x] == 6)
                        break;
                }
            }
            if ((camtype == 1 && camrot == 2) ||
                (camtype == 2 && camrot == 0) ||
                (camtype == 3 && camrot % 2) ||
                (camtype == 4 && camrot != 3) ||
                (camtype == 5)) // <-
            {
                int y = camera.first;
                int x = camera.second;
                while (y >= 0)
                {
                    temp[y][x] = '#';
                    y--;
                    if (y == -1 || temp[y][x] == 6)
                        break;
                }
            }
            if ((camtype == 1 && camrot == 3) ||
                (camtype == 2 && camrot == 1) ||
                (camtype == 3 && camrot > 1) ||
                (camtype == 4 && camrot != 0) ||
                (camtype == 5)) // 밑
            {
                int y = camera.first;
                int x = camera.second;
                while (x < m)
                {
                    temp[y][x] = '#';
                    x++;
                    if (x == m || temp[y][x] == 6)
                        break;
                }
            }
            if ((camtype == 1 && camrot == 1) ||
                (camtype == 2 && camrot == 1) ||
                (camtype == 3 && camrot < 2) ||
                (camtype == 4 && camrot != 2) ||
                (camtype == 5)) // 위
            {
                int y = camera.first;
                int x = camera.second;
                while (x >= 0)
                {
                    temp[y][x] = '#';
                    x--;
                    if (x == -1 || temp[y][x] == 6)
                        break;
                }
            }
            
            ret = std::min(dfs(temp, depth+1, cameras), ret);
        }
        return (ret);
    }
}

int main()
{
    // int n, m;
    std::cin >> n >> m;
    // int map[10][10];
    memset(map, -1, sizeof(map));
    std::vector<std::pair<int, int>> cameras;

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            std::cin >> map[i][j];
            if (map[i][j] != 0 && map[i][j] != 6)
                cameras.push_back(std::make_pair(i, j));
        }
    }
    std::cout << dfs(map, 0, cameras);
    // int camrot = 0;
    // for (int i = 0; i < cameras.size(); i++)
    // {
    //     std::pair<int, int> camera = cameras[i];
    //     int camtype = map[camera.first][camera.second];
    //     if ((camtype == 1 && camrot == 0) ||
    //         (camtype == 2 && camrot == 0) ||
    //         (camtype == 3 && !(camrot % 2)) ||
    //         (camtype == 4 && camrot != 1) || camtype == 5) // ->
    //     {
    //         int y = camera.first;
    //         int x = camera.second;
    //         while (y < n)
    //         {
    //             map[y][x] = '#';
    //             y++;
    //             if (y == n || map[i][j] == 6)
    //                 break;
    //         }
    //     }
    //     if ((camtype == 1 && camrot == 2) ||
    //         (camtype == 2 && camrot == 0) ||
    //         (camtype == 3 && camrot % 2) ||
    //         (camtype == 4 && camrot != 3) ||
    //         (camtype == 5)) // <-
    //     {
    //         int y = camera.first;
    //         int x = camera.second;
    //         while (y >= 0)
    //         {
    //             map[y][x] = '#';
    //             y--;
    //             if (y == -1 || map[y][x] == 6)
    //                 break;
    //         }
    //     }
    //     if ((camtype == 1 && camrot == 3) ||
    //         (camtype == 2 && camrot == 1) ||
    //         (camtype == 3 && camrot > 1) ||
    //         (camtype == 4 && camrot != 0) ||
    //         (camtype == 5)) // 밑
    //     {
    //         int y = camera.first;
    //         int x = camera.second;
    //         while (x < m)
    //         {
    //             map[y][x] = '#';
    //             x++;
    //             if (x == m || map[y][x] == 6)
    //                 break;
    //         }
    //     }
    //     if ((camtype == 1 && camrot == 1) ||
    //         (camtype == 2 && camrot == 1) ||
    //         (camtype == 3 && camrot < 2) ||
    //         (camtype == 4 && camrot != 2) ||
    //         (camtype == 5)) // 위
    //     {
    //         int y = camera.first;
    //         int x = camera.second;
    //         while (x >= 0)
    //         {
    //             map[y][x] = '#';
    //             x--;
    //             if (x == -1 || map[y][x] == 6)
    //                 break;
    //         }
    //     }
    // }
}

 

코드가 겁나 긴데, 밑 주석 부분은 맨 처음에 잘못 생각했던 탐색이었다. 그래도 그 코드를 토대로 DFS 구현을 잘 해서 한번에 성공했습니다 띄워서 기분이 좋다. 구현쪽은 큰 예외만 아니면 잘 잡히는 것 같다.

 

오늘도 평온한 하루가 되길. 슨민.