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


각각의 행과 열에대해서 인덱스가 증가하는 방향으로 한 번, 감소하는 방향으로 두 번 탐색을 진행하면서 예외 처리를 해주었다.


같은 높이가 몇개가 연속되는지 찾아서, 입력으로 주어지는 L과 비교하는 것이 관건인데, 1 1 2 2 이런식으로 증가하는 값에 대한 것은 그 개수를 파악하기 쉽지만, 2 2 1 1 이런식의 수열을 왼쪽에서 순서대로 탐색하면, 번거롭기 때문에 그냥 뒤에서부터도 연속되는 개수를 새서 경우를 따졌다.


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
/*
cnt == n이면 경로 확정
루프시작 인덱스로 다시 돌아오면 가능 확정
차이가 2이상이면 경로 불가능 확정
cnt < len 인데 증가하면 불가능 확정
경사로 설치한 곳에 또 설치하려고 하면 불가능 확정
*/
#include<iostream>
using namespace std;
int n, len, m[102][102], Rchk[102], Cchk[102];
bool vis[102][102];
int main(void) {
    cin >> n >> len;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> m[i][j];
    
    for (int i = 0; i < n; i++) {
        int cnt = 1;
        for (int j = 1; j < n ; j++) { //col 증가
            if (m[i][j] == m[i][j - 1]) cnt++; //cnt == len이면 확정 -> chk = 1로
            else if (m[i][j] - m[i][j - 1] >= 2) {
                Rchk[i] = -1;
                break;
            }
            else if (m[i][j] > m[i][j - 1] && cnt < len) {
                Rchk[i] = -1;
                break;
            }
            else if (m[i][j] - m[i][j - 1] == 1 && cnt >= len) {
                for (int k = j - 1; k >= j - len; k--) {
                    vis[i][k] = true;
                }
                cnt = 1;
            }
            else if (m[i][j] < m[i][j - 1]) cnt = 1;
            
        }
        if (cnt == n) {
            Rchk[i] = 1;
            continue;
        }
        
        //col 감소
        if (Rchk[i] == -1 || Rchk[i] == 1) continue; //이미 위에서 확정 했으면 스킵
        cnt = 1;
        for (int j = n - 2; j >= 0; j--) {
            bool endFlag = false;
            if (m[i][j] == m[i][j + 1]) cnt++;
            else if (m[i][j] - m[i][j + 1] >= 2) {
                Rchk[i] = -1;
                break;
            }
            else if (m[i][j] > m[i][j + 1] && cnt < len) {
                Rchk[i] = -1;
                break;
            }
            else if (m[i][j] - m[i][j + 1] == 1 && cnt >= len) {
                for (int k = j + 1; k <= j + len; k++) {
                    if (vis[i][k]) {//설치한 곳에 또 설치하려고 하는 경우
                        Rchk[i] = -1;
                        endFlag = true;
                        break;
                    }
                    else
                        vis[i][k] = true;
                }
                if (endFlag) break;
                cnt = 1;
            }
            else if (m[i][j] < m[i][j + 1]) cnt = 1;
            if (j == 0) Rchk[i] = 1;
        }
    }
 
    
    //경사로 놨던거 초기화
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++)
            vis[i][j] = false;
    }
 
 
    for (int i = 0; i < n; i++) {
        int cnt = 1;
        for (int j = 1; j < n; j++) { //col 증가
            if (m[j][i] == m[j-1][i]) cnt++; //cnt == len이면 확정 -> chk = 1로
            else if (m[j][i] - m[j-1][i] >= 2) {
                Cchk[i] = -1;
                break;
            }
            else if (m[j][i] > m[j-1][i] && cnt < len) {
                Cchk[i] = -1;
                break;
            }
            else if (m[j][i] - m[j-1][i] == 1 && cnt >= len) {
                for (int k = j - 1; k >= j - len; k--) {
                    vis[k][i] = true;
                }
                cnt = 1;
            }
            else if (m[j][i] < m[j-1][i]) cnt = 1;
 
 
        }
        if (cnt == n) {
            Cchk[i] = 1;
            continue;
        }
 
        //col 감소
        if (Cchk[i] == -1 || Cchk[i] == 1) continue; //이미 위에서 확정 했으면 스킵
        cnt = 1;
        for (int j = n - 2; j >= 0; j--) {
            bool endFlag = false;
            if (m[j][i] == m[j+1][i]) cnt++;
            else if (m[j][i] - m[j+1][i] >= 2) {
                Cchk[i] = -1;
                break;
            }
            else if (m[j][i] > m[j+1][i] && cnt < len) {
                Cchk[i] = -1;
                break;
            }
            else if (m[j][i] - m[j+1][i] == 1 && cnt >= len) {
                for (int k = j + 1; k <= j + len; k++) {
                    if (vis[k][i]) {//설치한 곳에 또 설치하려고 하는 경우
                        Cchk[i] = -1;
                        endFlag = true;
                        break;
                    }
                    else
                        vis[k][i] = true;
                }
                if (endFlag) 
                    break;
                
                cnt = 1;
            }
            else if (m[j][i] < m[j+1][i]) cnt = 1;
            if (j == 0) Cchk[i] = 1;
        }
    }
    
    int res = 0;
    for (int i = 0; i < n; i++) {
        if (Rchk[i] == 1) res++;
        if (Cchk[i] == 1) res++;
    }
    cout << res;
 
    return 0;
}
 
cs


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

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 17069번: 파이프 옮기기 2 (C++)  (0) 2019.08.09
백준 17070번: 파이프 옮기기 1 (C++)  (0) 2019.08.09
백준 14889번: 스타트와 링크 (C++)  (0) 2019.08.07
백준 14891번: 톱니바퀴 (C++)  (0) 2019.08.07
백준 15683번: 감시 (C++)  (0) 2019.08.07

기본적으로 #include<cstdlib> 헤더를 포함시켜서 사용한다.


floating type에 대해서는 cmath 헤더에도 오버로딩 되어있다고 한다.



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

'Programming Language > C++' 카테고리의 다른 글

string 대소문자 변환  (0) 2019.08.25
priority_queue  (0) 2019.08.14
(C++) list STL 출력 및 iterator  (0) 2019.08.04
next_permutation  (0) 2019.07.21
vector reverse  (0) 2019.07.04

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


순열과 조합을 적절히 사용해주면 되는 문제였다.


먼저 팀을 나누기 위해서는 순서는 중요하지 않기 때문에 조합으로 뽑는다.


0, 1, 2, 3, 4, 5 이렇게 6명의 사람이 있으면 조합으로 3개를 뽑아서 두 개의 팀을 만들어 준다.


이어서 팀 각각에 대해서 보자.


예를 들어 스타트 팀이 0, 1, 2로 결정되면 링크 팀은 자연스럽게 3, 4, 5로 결정된다.


이제 팀 각각에 대해서 점수를 계산해주면 된다.


S01과 S10이 다르다고 했다. 따라서 스타트팀의 경우에 대해서 순열로 뽑아준다. 총 3P2가지가 나올 것이다.


이를 더해서 점수 하나를 만들어주고, 링크팀에 대해서도 진행해준다. 이제 점수차이의 최솟값을 찾으면 된다.



점수 계산시 순열을 사용하지 않고, 조합으로 뽑은 이후에, 순서를 뒤집어서 계산을 추가해줘도 동일한 결과가 나온다. 하지만 순열로 처리하면 한 번에 처리할 수 있기 때문에 순열을 사용했다.



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
#include<iostream>
#include<vector>
#include<cstdlib>
#include<algorithm>
using namespace std;
int n, m[21][21], st = 0, arr[11], sco[11]; //arr이 팀1, sco가 자리순열
vector<int> v; //팀2
 
bool isused[21], isused2[11];
int Sum = 0, Sum2 = 0, res = 200;
void cntScore(int k, int a[]) { //스타트팀에 대한 점수 계산, 순열로 한다.
    
    if (k == 2) {
    
        Sum += m[sco[0]][sco[1]];
        return;
    }
    for (int i = 0; i < n / 2; i++) {
        if (!isused2[i]) {
            sco[k] = a[i];
            isused2[i] = true;
            cntScore(k + 1, a);
            isused2[i] = false;
        }
    }
}
void cntScore2(int k) { // 링크팀에 대한 점수 계산, 순열로 한다.
    
    if (k == 2) {
        
        Sum2 += m[sco[0]][sco[1]];
        return;
    }
    for (int i = 0; i < n / 2; i++) {
        if (!isused2[i]) {
            sco[k] = v[i];
            isused2[i] = true;
            cntScore2(k + 1);
            isused2[i] = false;
        }
    }
}
void makeTeam(int k) { //팀 선택은 조합으로 한다.
    if (k == n / 2) {
 
        for (int i = 0; i < n; i++) //팀1에서 선택 안 된 애들이 팀2로
            if (!isused[i]) v.push_back(i);
        
        cntScore(0, arr); //팀1 점수 계산
        
        cntScore2(0); //팀2 점수 계산
        
        res = min(res, abs(Sum - Sum2));
        Sum = 0, Sum2 = 0;
        v.clear();
 
        return;
    }
 
    if (k == 0) st = 0;
    for (int i = st; i < n; i++) {
        if (!isused[i]) {
            arr[k] = i;
            st = i;
            isused[i] = true;
            makeTeam(k + 1);
            isused[i] = false;
        }
    }
}
int main(void) {
    ios::sync_with_stdio(false);
    cin >> n;
 
    for (int i = 0; i < n; i++) 
        for (int j = 0; j < n; j++)
            cin >> m[i][j];
    
    makeTeam(0);
    cout << res;
    return 0;
}
cs



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

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 17070번: 파이프 옮기기 1 (C++)  (0) 2019.08.09
백준 14890번: 경사로 (C++)  (0) 2019.08.09
백준 14891번: 톱니바퀴 (C++)  (0) 2019.08.07
백준 15683번: 감시 (C++)  (0) 2019.08.07
백준 14502번: 연구소 (C++)  (0) 2019.08.07

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



문제를 보면, 톱니가 돌아가는 연산은 시계 방향으로 돌리거나 반시계 방향으로 돌리거나 둘 중 하나이다.


덮어 씌워지는 인덱스가 어떤 것인지 유의하면서 톱니의 회전을 구현해준 이후에는, 문제의 조건에 맞게 상황을 구현해주면 된다.


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
#include<iostream>
 
using namespace std;
 
int ring[5][9]; //1~4, 0~7
void rotate(int idx, int dir) {
    if (dir == -1) {//반시계
        
        int tmp = ring[idx][7];
        for (int i = 0; i <= 6; i++) {
            int move = i - 1;
            if (move < 0) move = 7;
            ring[idx][move] = ring[idx][i];
        }
        ring[idx][6] = tmp;
    }
    else if (dir == 1) {    //시계
        int tmp = ring[idx][7];
        for (int i = 6; i >= 0; i--) {
            int move = i + 1;
            ring[idx][move] = ring[idx][i];
        }
        ring[idx][0] = tmp;
    }
}
void process(int idx, int dir) {
 
    if (idx ==1) { //1번 톱니
        bool re2 = false; //또 돌려야 하는지
        if (ring[idx][2] != ring[idx + 1][6]) re2 = true; //접점 극 다르면 또 돌리기
        
        rotate(idx, dir);
        
        //또돌리는 처리
        if (re2) {
            bool re3 = false;
            if (ring[2][2] != ring[3][6]) re3 = true;
            //3번이랑 접점 확인
            rotate(2, dir * -1);
            
            if (re3) {
                bool re4 = false;
                if (ring[3][2] != ring[4][6]) re4 = true;
                rotate(3, dir);
                
                if (re4) rotate(4, dir * -1);
            }
        }
    }
    
    else if (idx == 2) {
        bool re1 = false, re3 = false;
        if (ring[1][2] != ring[2][6]) re1 = true;
        if (ring[2][2] != ring[3][6]) re3 = true;
        rotate(2, dir);
        
        if (re1) rotate(1, dir * -1);
        
        if (re3) {
            bool re4 = false;
            if (ring[3][2] != ring[4][6]) re4 = true;
            rotate(3, dir * -1);
            
            if (re4) rotate(4, dir);
        }
    }
    
    else if (idx == 3) {
        bool re2 = false, re4 = false;
        if (ring[2][2] != ring[3][6]) re2 = true;
        if (ring[3][2] != ring[4][6]) re4 = true;
        rotate(3, dir);
        
        if (re2) {
            bool re1 = false;
            if (ring[2][6] != ring[1][2]) re1 = true;
            rotate(2, dir * -1);
            if (re1) rotate(1, dir);
        }
        if (re4) rotate(4, dir * -1);
    }
    else if (idx == 4) {
        bool re3 = false;
        if (ring[4][6] != ring[3][2]) re3 = true;
        rotate(4, dir);
        if (re3) {
            bool re2 = false;
            if (ring[3][6] != ring[2][2]) re2 = true;
            rotate(3, dir * -1);
            if (re2) {
                bool re1 = false;
                if (ring[2][6] != ring[1][2]) re1 = true;
                rotate(2, dir);
                if (re1) rotate(1, dir * -1);
            }
        }
    }
}
 
int main(void) {
    for (int i = 1; i <= 4; i++)
        for (int j = 0; j < 8; j++)
            scanf("%1d", &ring[i][j]);
 
    int num;
    cin >> num;
    while (num--) {
        int idx, dir;
        cin >> idx >> dir;
        process(idx, dir);
    }
    int score = 0;
    for (int i = 1; i <= 4; i++) {
        if (ring[i][0] == 1 && i == 1) score++;
        else if (ring[i][0] == 1 && i == 2) score+= 2;
        else if (ring[i][0] == 1 && i == 3) score+= 4;
        else if (ring[i][0] == 1 && i == 4) score+= 8;
    }
    cout << score;
    return 0;
}
cs


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

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 14890번: 경사로 (C++)  (0) 2019.08.09
백준 14889번: 스타트와 링크 (C++)  (0) 2019.08.07
백준 15683번: 감시 (C++)  (0) 2019.08.07
백준 14502번: 연구소 (C++)  (0) 2019.08.07
백준 15685번: 드래곤 커브 (C++)  (0) 2019.08.06

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



문제를 보면, 카메라의 전체 개수가 8개로 많지 않다. 카메라의 종류별로 가능한 각도들을 모두 시뮬레이션해주면 되겠다.


각각의 카메라가 가질 수 있는 상태를 번호로 지정했다. 1번 카메라는 0~3번 상태, 2번 카메라는 4번~5번 상태... 이런 방식이다.


이제 카메라들이 띄고 있을 수 있는 상태를 조합으로 뽑아주면 된다.



이때 1번 카메라는 0~3번 밖에 쓸 수 없는 것처럼, 각 카메라별로 가능한 상태(인덱스)가 정해져 있기 때문에, 조합을 카메라에 대해서 먼저 해주고, 그리고 카메라의 상태에 대해서 이어서 해주어야한다.



작게 동, 서, 남, 북 방향으로 뻗어가는 방식인데, 카메라에 따라서 동시에 동서, 동남, 동서남 이런식으로 여러가지 상태를 가진다.


즉 동, 서, 남, 북 네가지 방향에 대한 처리만 정확하게 구현하면, 나머지는 그냥 그대로 코드를 사용하면 된다.



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
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
#include<iostream>
#include<vector>
 
using namespace std;
 
int R, C, map[10][10], tmp[10][10];
struct CAMPOS {
    int idx; //카메라 번호
    int r;
    int c;
};
vector<CAMPOS> cv;
bool isused[10][4]; //카메라 8개, 각도 사용 정보
bool masterUsage[9];
int cam[10][4]; //i번째 순서 카메라가 가질 수 있는 각도 저장
int arr[10], st = 0, st2 = 0, res = 100;
void init() {
    for (int i = 0; i < 10; i++)
        for (int j = 0; j < 4; j++)
            cam[i][j] = -1;
}
 
void process() {
    //arr에 카메라 각도 번호
    for (int i = 0; i < cv.size(); i++) {
        int cr = cv[i].r;
        int cc = cv[i].c;
        if (arr[i] == 0) {
            for (int j = cv[i].c + 1; j <= C - 1; j++) {//동
                if (map[cv[i].r][j] != 0 && map[cv[i].r][j] != 6) continue; //빈공간X and 벽X -> 카메라면 스킵
                if (map[cv[i].r][j] == 6) break;
                if (map[cv[i].r][j] == 0) map[cv[i].r][j] = 7; //감시 가능 영역을 7
            }
        }
        else if (arr[i] == 1) {
            for (int j = cv[i].r + 1; j <= R - 1; j++) {//남
                if (map[j][cv[i].c] != 0 && map[j][cv[i].c] != 6) continue; //빈공간X and 벽X -> 카메라면 스킵
                if (map[j][cv[i].c] == 6) break;
                if (map[j][cv[i].c] == 0) map[j][cv[i].c] = 7; //감시 가능 영역을 7
            }
        }
        else if (arr[i] == 2) {
            for (int j = cc - 1; j >= 0; j--) {//서
                if (map[cr][j] != 0 && map[cr][j] != 6) continue;
                if (map[cr][j] == 6) break;
                if (map[cr][j] == 0) map[cr][j] = 7;
            }
        }
        else if (arr[i] == 3) {
            for (int j = cr - 1; j >= 0; j--) {//북
                if (map[j][cc] != 0 && map[j][cc] != 6) continue;
                if (map[j][cc] == 6) break;
                if (map[j][cc] == 0) map[j][cc] = 7;
            }
        }
        else if (arr[i] == 4) {
            for (int j = cv[i].c + 1; j <= C - 1; j++) {//동
                if (map[cv[i].r][j] != 0 && map[cv[i].r][j] != 6) continue; //빈공간X and 벽X -> 카메라면 스킵
                if (map[cv[i].r][j] == 6) break;
                if (map[cv[i].r][j] == 0) map[cv[i].r][j] = 7; //감시 가능 영역을 7
            }
            for (int j = cc - 1; j >= 0; j--) {//서
                if (map[cr][j] != 0 && map[cr][j] != 6) continue;
                if (map[cr][j] == 6) break;
                if (map[cr][j] == 0) map[cr][j] = 7;
            }
        }
        else if (arr[i] == 5) {
            for (int j = cv[i].r + 1; j <= R - 1; j++) {//남
                if (map[j][cv[i].c] != 0 && map[j][cv[i].c] != 6) continue; //빈공간X and 벽X -> 카메라면 스킵
                if (map[j][cv[i].c] == 6) break;
                if (map[j][cv[i].c] == 0) map[j][cv[i].c] = 7; //감시 가능 영역을 7
            }
            for (int j = cr - 1; j >= 0; j--) {//북
                if (map[j][cc] != 0 && map[j][cc] != 6) continue;
                if (map[j][cc] == 6) break;
                if (map[j][cc] == 0) map[j][cc] = 7;
            }
        }
        else if (arr[i] == 6) {
            for (int j = cr - 1; j >= 0; j--) {//북
                if (map[j][cc] != 0 && map[j][cc] != 6) continue;
                if (map[j][cc] == 6) break;
                if (map[j][cc] == 0) map[j][cc] = 7;
            }
            for (int j = cv[i].c + 1; j <= C - 1; j++) {//동
                if (map[cv[i].r][j] != 0 && map[cv[i].r][j] != 6) continue; //빈공간X and 벽X -> 카메라면 스킵
                if (map[cv[i].r][j] == 6) break;
                if (map[cv[i].r][j] == 0) map[cv[i].r][j] = 7; //감시 가능 영역을 7
            }
        }
        else if (arr[i] == 7) {
            for (int j = cv[i].c + 1; j <= C - 1; j++) {//동
                if (map[cv[i].r][j] != 0 && map[cv[i].r][j] != 6) continue; //빈공간X and 벽X -> 카메라면 스킵
                if (map[cv[i].r][j] == 6) break;
                if (map[cv[i].r][j] == 0) map[cv[i].r][j] = 7; //감시 가능 영역을 7
            }
            for (int j = cv[i].r + 1; j <= R - 1; j++) {//남
                if (map[j][cv[i].c] != 0 && map[j][cv[i].c] != 6) continue; //빈공간X and 벽X -> 카메라면 스킵
                if (map[j][cv[i].c] == 6) break;
                if (map[j][cv[i].c] == 0) map[j][cv[i].c] = 7; //감시 가능 영역을 7
            }
        }
        else if (arr[i] == 8) {
            for (int j = cv[i].r + 1; j <= R - 1; j++) {//남
                if (map[j][cv[i].c] != 0 && map[j][cv[i].c] != 6) continue; //빈공간X and 벽X -> 카메라면 스킵
                if (map[j][cv[i].c] == 6) break;
                if (map[j][cv[i].c] == 0) map[j][cv[i].c] = 7; //감시 가능 영역을 7
            }
            for (int j = cc - 1; j >= 0; j--) {//서
                if (map[cr][j] != 0 && map[cr][j] != 6) continue;
                if (map[cr][j] == 6) break;
                if (map[cr][j] == 0) map[cr][j] = 7;
            }
        }
        else if (arr[i] == 9) {
            for (int j = cc - 1; j >= 0; j--) {//서
                if (map[cr][j] != 0 && map[cr][j] != 6) continue;
                if (map[cr][j] == 6) break;
                if (map[cr][j] == 0) map[cr][j] = 7;
            }
            for (int j = cr - 1; j >= 0; j--) {//북
                if (map[j][cc] != 0 && map[j][cc] != 6) continue;
                if (map[j][cc] == 6) break;
                if (map[j][cc] == 0) map[j][cc] = 7;
            }
        }
        else if (arr[i] == 10) {
            for (int j = cr - 1; j >= 0; j--) {//북
                if (map[j][cc] != 0 && map[j][cc] != 6) continue;
                if (map[j][cc] == 6) break;
                if (map[j][cc] == 0) map[j][cc] = 7;
            }
            for (int j = cv[i].c + 1; j <= C - 1; j++) {//동
                if (map[cv[i].r][j] != 0 && map[cv[i].r][j] != 6) continue; //빈공간X and 벽X -> 카메라면 스킵
                if (map[cv[i].r][j] == 6) break;
                if (map[cv[i].r][j] == 0) map[cv[i].r][j] = 7; //감시 가능 영역을 7
            }
            for (int j = cc - 1; j >= 0; j--) {//서
                if (map[cr][j] != 0 && map[cr][j] != 6) continue;
                if (map[cr][j] == 6) break;
                if (map[cr][j] == 0) map[cr][j] = 7;
            }
        }
        else if (arr[i] == 11) {
            for (int j = cr - 1; j >= 0; j--) {//북
                if (map[j][cc] != 0 && map[j][cc] != 6) continue;
                if (map[j][cc] == 6) break;
                if (map[j][cc] == 0) map[j][cc] = 7;
            }
            for (int j = cv[i].c + 1; j <= C - 1; j++) {//동
                if (map[cv[i].r][j] != 0 && map[cv[i].r][j] != 6) continue; //빈공간X and 벽X -> 카메라면 스킵
                if (map[cv[i].r][j] == 6) break;
                if (map[cv[i].r][j] == 0) map[cv[i].r][j] = 7; //감시 가능 영역을 7
            }
            for (int j = cv[i].r + 1; j <= R - 1; j++) {//남
                if (map[j][cv[i].c] != 0 && map[j][cv[i].c] != 6) continue; //빈공간X and 벽X -> 카메라면 스킵
                if (map[j][cv[i].c] == 6) break;
                if (map[j][cv[i].c] == 0) map[j][cv[i].c] = 7; //감시 가능 영역을 7
            }
        }
        else if (arr[i] == 12) {
            for (int j = cv[i].c + 1; j <= C - 1; j++) {//동
                if (map[cv[i].r][j] != 0 && map[cv[i].r][j] != 6) continue; //빈공간X and 벽X -> 카메라면 스킵
                if (map[cv[i].r][j] == 6) break;
                if (map[cv[i].r][j] == 0) map[cv[i].r][j] = 7; //감시 가능 영역을 7
            }
            for (int j = cv[i].r + 1; j <= R - 1; j++) {//남
                if (map[j][cv[i].c] != 0 && map[j][cv[i].c] != 6) continue; //빈공간X and 벽X -> 카메라면 스킵
                if (map[j][cv[i].c] == 6) break;
                if (map[j][cv[i].c] == 0) map[j][cv[i].c] = 7; //감시 가능 영역을 7
            }
            for (int j = cc - 1; j >= 0; j--) {//서
                if (map[cr][j] != 0 && map[cr][j] != 6) continue;
                if (map[cr][j] == 6) break;
                if (map[cr][j] == 0) map[cr][j] = 7;
            }
        }
        else if (arr[i] == 13) {
            for (int j = cv[i].r + 1; j <= R - 1; j++) {//남
                if (map[j][cv[i].c] != 0 && map[j][cv[i].c] != 6) continue; //빈공간X and 벽X -> 카메라면 스킵
                if (map[j][cv[i].c] == 6) break;
                if (map[j][cv[i].c] == 0) map[j][cv[i].c] = 7; //감시 가능 영역을 7
            }
            for (int j = cc - 1; j >= 0; j--) {//서
                if (map[cr][j] != 0 && map[cr][j] != 6) continue;
                if (map[cr][j] == 6) break;
                if (map[cr][j] == 0) map[cr][j] = 7;
            }
            for (int j = cr - 1; j >= 0; j--) {//북
                if (map[j][cc] != 0 && map[j][cc] != 6) continue;
                if (map[j][cc] == 6) break;
                if (map[j][cc] == 0) map[j][cc] = 7;
            }
        }
        else if (arr[i] == 14) {
            for (int j = cv[i].r + 1; j <= R - 1; j++) {//남
                if (map[j][cv[i].c] != 0 && map[j][cv[i].c] != 6) continue; //빈공간X and 벽X -> 카메라면 스킵
                if (map[j][cv[i].c] == 6) break;
                if (map[j][cv[i].c] == 0) map[j][cv[i].c] = 7; //감시 가능 영역을 7
            }
            for (int j = cc - 1; j >= 0; j--) {//서
                if (map[cr][j] != 0 && map[cr][j] != 6) continue;
                if (map[cr][j] == 6) break;
                if (map[cr][j] == 0) map[cr][j] = 7;
            }
            for (int j = cr - 1; j >= 0; j--) {//북
                if (map[j][cc] != 0 && map[j][cc] != 6) continue;
                if (map[j][cc] == 6) break;
                if (map[j][cc] == 0) map[j][cc] = 7;
            }
            for (int j = cv[i].c + 1; j <= C - 1; j++) {//동
                if (map[cv[i].r][j] != 0 && map[cv[i].r][j] != 6) continue; //빈공간X and 벽X -> 카메라면 스킵
                if (map[cv[i].r][j] == 6) break;
                if (map[cv[i].r][j] == 0) map[cv[i].r][j] = 7; //감시 가능 영역을 7
            }
        }
    }
}
void backTracking(int k) {
    if (k == cv.size()) {
 
        process();
 
        //사각지대 계산
        int cnt = 0;
        for (int i = 0; i < R; i++)
            for (int j = 0; j < C; j++)
                if (map[i][j] == 0) cnt++;
 
        if (res > cnt) 
            res = cnt;
 
        //원상복구
        for (int i = 0; i < R; i++)
            for (int j = 0; j < C; j++)
                map[i][j] = tmp[i][j];
        return;
    }
 
    if (k == 0) st = 0;
 
    for (int i = st; i < cv.size(); i++) {
        if (!masterUsage[i]) {
            masterUsage[i] = true;
            //i번카메라가 사용중이 아니면서
            //if (k == 0) st2 = 0;
            for (int j = 0; j < 4; j++) {
                if (cam[i][j] != -1 && !isused[i][j]) {
                    //존재하는 카메라 각도이면서 사용중이 아닌 각도라면
                    arr[k] = cam[i][j];
                    isused[i][j] = true;
                    st = i;
                    //st2 = j;
                    backTracking(k + 1);
                    isused[i][j] = false;
                }
            }
            masterUsage[i] = false;
        }
 
    }
 
}
int main(void) {
    ios::sync_with_stdio(false);
 
    cin >> R >> C;
    for (int i = 0; i < R; i++)
        for (int j = 0; j < C; j++) {
            cin >> map[i][j];
            tmp[i][j] = map[i][j];
            if (map[i][j] != 0 && map[i][j] != 6) {
                CAMPOS tmp;
                tmp.r = i;
                tmp.c = j;
                tmp.idx = map[i][j];
                cv.push_back(tmp); //cv에 카메라 정보 저장
            }
        }
 
    init();
 
    for (int i = 0; i < cv.size(); i++) {
        if (cv[i].idx == 1) {
            for (int j = 0; j < 4; j++)
                cam[i][j] = j;
        }
        else if (cv[i].idx == 2) {
            for (int j = 0; j < 2; j++)
                cam[i][j] = j + 4;
        }
        else if (cv[i].idx == 3) {
            for (int j = 0; j < 4; j++)
                cam[i][j] = j + 6;
        }
        else if (cv[i].idx == 4) {
            for (int j = 0; j < 4; j++)
                cam[i][j] = j + 10;
        }
        else if (cv[i].idx == 5) {
            cam[i][0] = 14;
        }
    }
 
    backTracking(0);
    cout << res << '\n';
 
}
cs


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

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 14889번: 스타트와 링크 (C++)  (0) 2019.08.07
백준 14891번: 톱니바퀴 (C++)  (0) 2019.08.07
백준 14502번: 연구소 (C++)  (0) 2019.08.07
백준 15685번: 드래곤 커브 (C++)  (0) 2019.08.06
백준 15686번: 치킨 배달 (C++)  (0) 2019.08.05

+ Recent posts

티스토리툴바