티스토리 뷰

ALGORITHM

백준 / 15683번 / 감시 / C++

chrisysl 2019. 2. 19. 21:30

# 출처 : https://www.acmicpc.net/problem/15683




dir 이라는 변수로 상,하,좌,우 배열을 모두 확인하는것이나, rotation이라는 배열을 둬서 회전 시킬 최대 크기를 손쉽게 설정하는법 같은 

기술들이 많이 녹아들어가 있다. 




# 풀이

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
#include <iostream>
#define endl '\n'
using namespace std;
 
struct CCTV
{
    int type, r, c;
};
int N, M, ans = 1e9, map[8][8];
int cctv_size;
CCTV cctv[8];
const int rotation[] = { NULL42441 };
 
void map_cpy(int desc[8][8], int src[8][8])
{
    for (int r = 0; r < N; ++r)
        for (int c = 0; c < M; ++c)
            desc[r][c] = src[r][c];
}
// update 함수는 한 방향으로만 감시를 해 주는 함수.
void update(int dir, CCTV cctv)
{
    // cctv를 기준으로 dir 방향에 대한 체크를 한다.
    // dir = 0 : 동, 1 : 북, 2 : 서, 3 : 남
    dir %= 4;    // dir값이 4보다 큰 값이 들어올 수 있으므로
    if (dir == 0)            // 동쪽
    {
        for (int c = cctv.c + 1; c < M; ++c)
        {
            if (map[cctv.r][c] == 6break;
            map[cctv.r][c] = -1;
        }
    }
    else if (dir == 1)    // 북쪽
    {
        for (int r = cctv.r - 1; r >= 0--r)
        {
            if (map[r][cctv.c] == 6break;
            map[r][cctv.c] = -1;
        }
    }
    else if (dir == 2)    // 서쪽
    {
        for (int c = cctv.c - 1; c >= 0--c)
        {
            if (map[cctv.r][c] == 6break;
            map[cctv.r][c] = -1;
        }
    }
    else if (dir == 3)    // 남쪽
    {
        for (int r = cctv.r + 1; r < N; ++r)
        {
            if (map[r][cctv.c] == 6break;
            map[r][cctv.c] = -1;
        }
    }
}
void DFS(int cctv_idx)
{
    if (cctv_idx == cctv_size)
    {
        int cnt = 0;
        // 0의 개수 count
        for (int r = 0; r < N; ++r)
        {
            for (int c = 0; c < M; ++c)
            {
                if (map[r][c] == 0)
                    ++cnt;
            }
        }
        if (ans > cnt)
            ans = cnt;
        return;
    }
    int backup[8][8];
    int type = cctv[cctv_idx].type;
 
    for (int dir = 0; dir < rotation[type]; ++dir)
    {
        // map 백업
        map_cpy(backup, map);
 
        // map 업데이트
        // update 함수는 한 방향만 갱신하는 함수.
        // 따라서 이 함수를 필요에 맞게 호출해 주면 됨.
        if (type == 1)            // 1번 카메라는 한 방향 감시이니 하나만 불러줌.
        {
            update(dir, cctv[cctv_idx]);
        }
        else if (type == 2)        // 2번 카메라는 기본방향과 그 180도 반대방향을 감시함.
        {
            update(dir, cctv[cctv_idx]);
            update(dir + 2, cctv[cctv_idx]);
        }
        else if (type == 3)        // 3번 카메라는 기본방향과 90도 방향을 감시함.
        {
            update(dir, cctv[cctv_idx]);
            update(dir + 1, cctv[cctv_idx]);
        }
        else if (type == 4)        // 4번 카메라는 기본방향과 90도, 180도 방향을 감시함
        {
            update(dir, cctv[cctv_idx]);
            update(dir + 1, cctv[cctv_idx]);
            update(dir + 2, cctv[cctv_idx]);
        }
        else if (type == 5)        // 5번 카메라는 전 방향 모두 감시함
        {
            update(dir, cctv[cctv_idx]);
            update(dir + 1, cctv[cctv_idx]);
            update(dir + 2, cctv[cctv_idx]);
            update(dir + 3, cctv[cctv_idx]);
        }
 
        DFS(cctv_idx + 1);
 
        // map 복원 - 백트래킹
        map_cpy(map, backup);
    }
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
 
    cin >> N >> M;
    for (int r = 0; r < N; ++r)
    {
        for (int c = 0; c < M; ++c)
        {
            cin >> map[r][c];
            if (map[r][c] != 0 && map[r][c] != 6)
            {
                cctv[cctv_size].r = r;
                cctv[cctv_size].c = c;
                cctv[cctv_size].type = map[r][c];
                ++cctv_size;
            }
        }
    }
    DFS(0);
    cout << ans << endl;
    return 0;
}
cs


댓글
댓글쓰기 폼
공지사항
Total
290,627
Today
19
Yesterday
32
링크
TAG
more
«   2022/08   »
  1 2 3 4 5 6
7 8 9 10 11 12 13
14 15 16 17 18 19 20
21 22 23 24 25 26 27
28 29 30 31      
글 보관함