YoonWould!!

[삼성SWTest준비] 15683번 감시 본문

<SW>/알고리즘 + 자료구조

[삼성SWTest준비] 15683번 감시

Hading 2018. 10. 17. 13:57
728x90

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


삼성SW 기출 문제 한 번에 보기 : https://www.acmicpc.net/workbook/view/1152




※삼성 SW 역량평가 기출문제 어떻게 풀지?※


1. 문제 이해
 - 사각지대의 최소크기 구하라
 - CCTV 개수는 8개 이하


2. 어떻게 품?

 - 재귀함수로 4가지 방향 중복 순열 만든다.
 - 계속해서 지도 갱신
 - 최소 사각지대 수 갱신


※필요 역량 정리하기!!!※

1. 중복 순열 

2. 결국, 브루트 포스


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
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
/*
감시
*/
#include<iostream>
#include<vector>
#include <algorithm>
 
using namespace std;
int n, m;
int result;
int cctv_size;
int map[8][8];
int test[8][8];
 
struct info {
    int x;
    int y;
    int dir;
    int type;
};
 
void go0(int x, int y) {
    for (int j = y; j < m; j++) {
        if (test[x][j] == 6) break;
        if (test[x][j] == 0) test[x][j] = -1;
    }
}
void go1(int x, int y) {
    for (int i = x; i < n; i++) {
        if (test[i][y] == 6) break;
        if (test[i][y] == 0) test[i][y] = -1;
    }
}
void go2(int x, int y) {
    for (int j = y; j >= 0; j--) {
        if (test[x][j] == 6) break;
        if (test[x][j] == 0) test[x][j] = -1;
    }
}
void go3(int x, int y) {
    for (int i = x; i >= 0; i--) {
        if (test[i][y] == 6) break;
        if (test[i][y] == 0) test[i][y] = -1;
    }
 
}
void do_test(vector<info> &cctv) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            test[i][j] = map[i][j];
        }
    }
    for (int i = 0; i < cctv.size(); i++) {
        if (cctv[i].type == 1) {
            if (cctv[i].dir == 0) go0(cctv[i].x, cctv[i].y);
            if (cctv[i].dir == 1) go1(cctv[i].x, cctv[i].y);
            if (cctv[i].dir == 2) go2(cctv[i].x, cctv[i].y);
            if (cctv[i].dir == 3) go3(cctv[i].x, cctv[i].y);
        }
        if (cctv[i].type == 2) {
            if (cctv[i].dir == 0 || cctv[i].dir == 2) {
                go0(cctv[i].x, cctv[i].y);
                go2(cctv[i].x, cctv[i].y);
            }
 
            if (cctv[i].dir == 1 || cctv[i].dir == 3) {
                go1(cctv[i].x, cctv[i].y);
                go3(cctv[i].x, cctv[i].y);
            }
        }
        if (cctv[i].type == 3) {
            if (cctv[i].dir == 0) {
                go2(cctv[i].x, cctv[i].y);
                go3(cctv[i].x, cctv[i].y);
            }
 
            if (cctv[i].dir == 1) {
                go0(cctv[i].x, cctv[i].y);
                go3(cctv[i].x, cctv[i].y);
            }
 
            if (cctv[i].dir == 2) {
                go0(cctv[i].x, cctv[i].y);
                go1(cctv[i].x, cctv[i].y);
            }
 
            if (cctv[i].dir == 3) {
                go1(cctv[i].x, cctv[i].y);
                go2(cctv[i].x, cctv[i].y);
            }
        }
        if (cctv[i].type == 4) {
            if (cctv[i].dir == 0) {
                go0(cctv[i].x, cctv[i].y);
                go1(cctv[i].x, cctv[i].y);
                go2(cctv[i].x, cctv[i].y);
            }
 
            if (cctv[i].dir == 1) {
                go1(cctv[i].x, cctv[i].y);
                go2(cctv[i].x, cctv[i].y);
                go3(cctv[i].x, cctv[i].y);
            }
 
            if (cctv[i].dir == 2) {
                go0(cctv[i].x, cctv[i].y);
                go2(cctv[i].x, cctv[i].y);
                go3(cctv[i].x, cctv[i].y);
            }
 
            if (cctv[i].dir == 3) {
                go0(cctv[i].x, cctv[i].y);
                go1(cctv[i].x, cctv[i].y);
                go3(cctv[i].x, cctv[i].y);
            }
        }
        if (cctv[i].type == 5) {
            go0(cctv[i].x, cctv[i].y);
            go1(cctv[i].x, cctv[i].y);
            go2(cctv[i].x, cctv[i].y);
            go3(cctv[i].x, cctv[i].y);
        }
    }
 
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (test[i][j] == 0) cnt++;
        }
    }
 
    result = min(result, cnt);
}
 
void go(int index, vector<info> &cctv) {
 
    if (index == cctv_size) {
 
        do_test(cctv);
 
        return;
    }
 
    cctv[index].dir = 0;
    go(index + 1, cctv);
 
    cctv[index].dir = 1;
    go(index + 1, cctv);
 
    cctv[index].dir = 2;
    go(index + 1, cctv);
 
    cctv[index].dir = 3;
    go(index + 1, cctv);
}
 
int main() {
    result = 99999999;
    cin >> n >> m;
    vector<info> cctv;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> map[i][j];
 
            if (map[i][j] != 6 && map[i][j] > 0)
                cctv.push_back({i,j,0,map[i][j]});
        }
    }
    cctv_size = cctv.size();
    go(0,cctv);
 
    cout << result;
    return 0;
}
cs


728x90
저작자표시 비영리 변경금지

'<SW> > 알고리즘 + 자료구조' 카테고리의 다른 글

[삼성SWTest준비] 15685번 드래곤커브  (0) 2018.10.17
[재귀] 15651번 N과 M (3)  (0) 2018.10.17
[BFS] 숨바꼭질 4  (0) 2018.10.16
다익스트라(우선순위 힙이용)  (0) 2018.10.16
[다익스트라] 다익스트라 알고리즘 1  (0) 2018.10.09
'<SW>/알고리즘 + 자료구조' Related Articles more