[백준 15683번] 감시 C++

0. 과정

난이도 : 골드 4
풀이 방법 : DFS + BackTracking
해설:
기존에는 backtracking을 위해서 move에서 이동했던 것 만큼 다시 되돌려주었는데 
6 6
1 0 0 0 0 0
0 1 0 0 0 0
0 0 1 5 0 0
0 0 5 1 0 0
0 0 0 0 1 0
0 0 0 0 0 1
답 : 2

다음 input값에서 무한루프가 돌았다. 따라서 다른 사람들의 풀이를 참고하니 굳이 moveBackTracking()를 통해 되돌려주는 대신 tmp 배열을 이용해 기존 방문했던 visited 배열을 저장했다가 다시 되돌려주는 방식을 이용하였다.

 

1. 첫 번째 풀이

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

int n, m;
int pan[9][9];
int visited[9][9] = {
    0,
};
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

vector<pair<int, int>> cctv;

int res = INT_MAX;

void input()
{
    cin >> n >> m;

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> pan[i][j];

            if (pan[i][j] != 0 && pan[i][j] != 6)
            {
                cctv.push_back({i, j});
            }
            if (pan[i][j] != 0)
            {
                visited[i][j]++;
            }
        }
    }
}

void move(int x, int y, int dir)
{
    while (true)
    {
        int nx = x + dx[dir];
        int ny = y + dy[dir];

        if (nx >= 0 && nx < n && ny >= 0 && ny < m && pan[nx][ny] != 6)
        {
            visited[nx][ny]++;
            x = nx;
            y = ny;
        }
        else
        {
            break;
        }
    }
}

void moveBackTracking(int x, int y, int dir)
{
    while (true)
    {
        int nx = x + dx[dir];
        int ny = y + dy[dir];

        if (nx >= 0 && nx < n && ny >= 0 && ny < m && pan[nx][ny] != 6)
        {
            visited[nx][ny]--;
            x = nx;
            y = ny;
        }
        else
        {
            break;
        }
    }
}

void DFS(int L)
{

    if (L == cctv.size())
    {
        int ans = 0;
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                if (!visited[i][j])
                {
                    ans++;
                }
            }
        }

        res = min(res, ans);

        return;
    }

    for (int i = L; i < cctv.size(); i++)
    {
        int x = cctv[i].first;
        int y = cctv[i].second;

        if (pan[x][y] == 1)
        {
            for (int j = 0; j < 4; j++)
            {
                move(x, y, j);
                DFS(L + 1);
                moveBackTracking(x, y, j);
            }
        }
        else if (pan[x][y] == 2)
        {
            // 상하
            move(x, y, 0);
            move(x, y, 1);
            DFS(L + 1);
            moveBackTracking(x, y, 0);
            moveBackTracking(x, y, 1);

            // 좌우
            move(x, y, 2);
            move(x, y, 3);
            DFS(L + 1);
            moveBackTracking(x, y, 2);
            moveBackTracking(x, y, 3);
        }
        else if (pan[x][y] == 3)
        {
            // 상
            move(x, y, 0);
            for (int j = 2; j < 4; j++)
            {
                move(x, y, j);
                DFS(L + 1);
                moveBackTracking(x, y, j);
            }
            moveBackTracking(x, y, 0);

            // 하
            move(x, y, 1);
            for (int j = 2; j < 4; j++)
            {
                move(x, y, j);
                DFS(L + 1);
                moveBackTracking(x, y, j);
            }
            moveBackTracking(x, y, 1);
        }
        else if (pan[x][y] == 4)
        {
            for (int j = 0; j < 4; j++)
            {
                move(x, y, j);
            }
            for (int j = 0; j < 4; j++)
            {
                moveBackTracking(x, y, j);
                DFS(L + 1);
                move(x, y, j);
            }
            for (int j = 0; j < 4; j++)
            {
                moveBackTracking(x, y, j);
            }
        }
        else if (pan[x][y] == 5)
        {
            for (int j = 0; j < 4; j++)
            {
                move(x, y, j);
            }
            DFS(L + 1);
            for (int j = 0; j < 4; j++)
            {
                moveBackTracking(x, y, j);
            }
        }
    }
}

int main(int argc, char const *argv[])
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    input();
    DFS(0);

    cout << res;

    return 0;
}

2. 정답 풀이

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

int dx[] = {-1, 0, 1, 0}; // 상,우,하,좌
int dy[] = {0, 1, 0, -1};
int n, m; // 세로, 가로
int pan[9][9];
int visited[9][9] = {
    0,
};
vector<pair<int, int>> cctv;
int res = INT_MAX;

void input()
{
    cin >> n >> m;

    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
        {
            cin >> pan[i][j];

            if (pan[i][j] != 0)
            {
                visited[i][j] += 1;
                if (pan[i][j] != 6)
                    cctv.push_back({i, j});
            }
        }
}

void move(int x, int y, int dir)
{
    dir %= 4;
    while (true)
    {
        int nx = x + dx[dir];
        int ny = y + dy[dir];

        if (nx >= 0 && nx < n && ny >= 0 && ny < m && pan[nx][ny] != 6)
        {
            visited[nx][ny] += 1;
            x = nx;
            y = ny;
        }
        else
            break;
    }
}

void DFS(int L)
{
    if (L == cctv.size())
    {
        int ans = 0;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                if (visited[i][j] == 0)
                    ans++;
        res = min(res, ans);

        return;
    }

    int tmp[9][9];
    for (int k = 0; k < 4; k++)
    {

        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                tmp[i][j] = visited[i][j];

        int x = cctv[L].first;
        int y = cctv[L].second;

        if (pan[x][y] == 1)
        {
            move(x, y, k);
        }
        else if (pan[x][y] == 2)
        {
            move(x, y, k);
            move(x, y, k + 2);
        }
        else if (pan[x][y] == 3)
        {
            move(x, y, k);
            move(x, y, k + 1);
        }
        else if (pan[x][y] == 4)
        {
            move(x, y, k);
            move(x, y, k + 1);
            move(x, y, k + 2);
        }
        else if (pan[x][y] == 5)
        {
            move(x, y, k);
            move(x, y, k + 1);
            move(x, y, k + 2);
            move(x, y, k + 3);
        }

        DFS(L + 1);

        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                visited[i][j] = tmp[i][j];
    }
}
int main(int argc, char const *argv[])
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    input();
    DFS(0);
    cout << res;

    return 0;
}