'알고리즘 문제 풀이' 카테고리의 글 목록 (15 Page)

알고리즘 문제 풀이

백준 14890번: 경사로 (C++)

Hugxy 2019. 8. 9. 00:15

2019. 8. 9. 00:15

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;
}
 
Colored by Color Scripter
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

백준 14889번: 스타트와 링크 (C++)

Hugxy 2019. 8. 7. 22:36

2019. 8. 7. 22:36

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;
}
Colored by Color Scripter
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

백준 14891번: 톱니바퀴 (C++)

Hugxy 2019. 8. 7. 21:31

2019. 8. 7. 21:31

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;
}
Colored by Color Scripter
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

백준 15683번: 감시 (C++)

Hugxy 2019. 8. 7. 21:24

2019. 8. 7. 21:24

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';
 
}
Colored by Color Scripter
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

백준 14502번: 연구소 (C++)

Hugxy 2019. 8. 7. 01:04

2019. 8. 7. 01:04

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

조합과 bfs가 합쳐진 문제인 연구소 시리즈의 첫번째 문제이다.

다른 연구소 문제를 해결했다면, 비슷한 아이디어로 무난하게 해결할 수 있다.

알고리즘은 다음과 같다.

1. 빈 공간(0인 위치)를 벡터에 모두 담아놓고 그 중 세개를 조합으로 뽑는다.

2. 조합으로 뽑은 곳의 값을 1로 (벽으로) 변경해준 이후에 bfs를 수행한다.

3. 방문되지 않은 지점(바이러스가 퍼지지 않은 지점)이면서 빈 공간인 부분의 수를 계산한다.

4. 수정한 map과 방문처리 배열을 초기화 시켜준다.

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
//map에 1을 세개 두고, 만들 수 있는 0의 최대 개수
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
 
int R, C, m[9][9], arr[4];//빈공간 담은 벡터의 인덱스 저장
vector<pair<int, int> > v; //빈공간 저장 벡터
bool vis[9][9], isused[81];
int res = 0, st = 0;
queue<pair<int, int> > q;
int dr[4] = { 0,0,1,-1 };
int dc[4] = { 1,-1,0,0 };
void bfs(pair<int, int> start) {
    q.push({ start.first, start.second });
    vis[start.first][start.second] = true;
    while (!q.empty()) {
        pair<int, int> cur = q.front();
        q.pop();
        for (int i = 0; i < 4; i++) {
            int nr = cur.first + dr[i];
            int nc = cur.second + dc[i];
            if (nr < 0 || nc < 0 || nr >= R || nc >= C) continue;
            if (vis[nr][nc] || m[nr][nc] == 1) continue;
 
            q.push({ nr, nc });
            vis[nr][nc] = true;
        }
    }
}
void findSafe() {
    int cnt = 0;
    for (int i = 0; i < R; i++)
        for (int j = 0; j < C; j++)
            if (!vis[i][j] && m[i][j] == 0) cnt++; //빈칸이면서 바이러스가 퍼지지 않은 곳 = 안전지점
 
    if (res < cnt)
        res = cnt;
}
void init() {
    for (int i = 0; i < 3; i++) {
        int j = arr[i];
        m[v[j].first][v[j].second] = 0; //벽 세웠던 부분 다시 빈칸으로
    }
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            vis[i][j] = false;
        }
    }
}
void backTracking(int k) {
    if (k == 3) { //빈공간 중에서 세개 조합 뽑아서
        for (int i = 0; i < 3; i++) {
            int j = arr[i];
            m[v[j].first][v[j].second] = 1; //1로 바꿔주고
        }
 
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if (m[i][j] == 2 && !vis[i][j]) bfs({ i, j }); //bfs 실행
            }
        }
 
        findSafe(); //빈칸이면서 방문되지 않은 지점 검색
 
        init(); //map, vis 수정한 값 초기화
 
        return;
    }
    if (k == 0) st = 0;
    for (int i = st; i < v.size(); i++) {
        if (!isused[i]) {
            arr[k] = i;
            st = i;
            isused[i] = true;
            backTracking(k + 1);
            isused[i] = false;
        }
    }
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> R >> C;
 
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            cin >> m[i][j];
            if (m[i][j] == 0) v.push_back({ i, j }); //빈공간 인덱스 미리 저장
        }
    }
 
    backTracking(0); //빈공간 인덱스 조합 검사
 
    cout << res;
    return 0;
}
Colored by Color Scripter
cs

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

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

백준 14891번: 톱니바퀴 (C++) (0)	2019.08.07
백준 15683번: 감시 (C++) (0)	2019.08.07
백준 15685번: 드래곤 커브 (C++) (0)	2019.08.06
백준 15686번: 치킨 배달 (C++) (0)	2019.08.05
백준 17141번: 연구소 2 (C++) (0)	2019.08.05

백준 15685번: 드래곤 커브 (C++)

Hugxy 2019. 8. 6. 23:18

2019. 8. 6. 23:18

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

특별한 알고리즘이랄 것이 필요하지 않은 전형적인 시뮬레이션 문제였다.

하지만 설계를 제대로 하고 들어가지 않으면 꽤 해맬 수 있었던 문제이다.

여느 시뮬레이션 문제들이 그러하듯이, 상황을 어떻게 표현할 것인가 생각해야 한다.

나는 주의 깊게 그림을 살펴보지 않아서 간과했던 사실이지만, 문제 설명에서 그림을 보여주면서 좌표 값을 그림 아래에 표시해줬다.

그것을 보면, 커브의 상태를 좌표에 찍을 수 있고, 좌표에 어떻게 찍히느냐는 기본적으로 세대가 결정하고,

같은 세대라고 할지라도 시작한 방향값이 다르다면 다르게 찍힌다는 것을 알 수 있다.

(0,0)에서 시작한 0세대 커브는 (1,0)으로 x값이 1증가한다.

그리고 이어서 2세대로 변천할 때, 1세대의 마지막 점(1,0)에서 (1,-1)로 이동하여 y좌표가 1감소하는 것을 알 수 있다.

이 상황은 0,0에서 시작한 d값이 1인 0세대의 커브이다.

만약 나머지 조건이 동일하고, 방향 값인 d값이 1이었다면? 0,0에서 시작한 커브는 상단으로 뻗었을 것이고

0세대 커브는 0,0에서 0,-1로 변천했을 것이다. 이런식으로 파악해나가야 한다.

방향이 0인 세대별 커브의 성분을 방향 숫자로 나타내보면,

0세대: 0

1세대: 0, 1

2세대: 0, 1, 2, 1

3세대: 0, 1, 2, 1, 2, 3, 2, 1

4세대: 0, 1, 2, 1, 2, 3, 2, 1, 2, 3, 0, 3, 2, 3, 2, 1

...

이런식으로 증가한다. 여기서 규칙을 확인할 수 있다. 먼저 개수가 2의 거듭제곱 꼴로 늘어나고 있다.

그리고 문제에서 주어진 조건과 연결해서 확인해보면, 이전 세대의 커브를 90도 돌리고 끝을 붙인다고 했다.

90도 돌린다는 것은 방향값의 변화를 의미하는 것이고, 끝을 붙인다는 것은, 성분을 뒤에서부터 하나씩 붙인다는 것이다.

따라서 0세대에서 1세대로 갈 때, 0에 1을 더한 1이 붙은 것이고, 1세대에서 2세대로 갈 때, 1세대의 마지막인 1에 1을 더한 값인 2가 붙고, 0에 1을 더한 값인 1이 그 뒤에 붙은 것이다.

이를 그냥 배열 인덱스로 조절해서 구해도 되겠지만 동작 구조가 스택과 같으니, 스택을 활용했다.

나는 방향 0의 드래곤커브의 10세대를 구해서 배열에 저장했다. 10세대를 구하면 곧, 앞부분에 0~9세대도 포함되어 있는 것이기 때문에 변형해서 사용하면 된다. 또한 방향 0의 값을 구해 놓았으니, 방향이 변하면 모든 성분을 더해줘서 방향을 바뀐 것처럼 사용하면 되고, %4를 통해 값이 4를 넘어가지 않도록 유지해줘야 하겠다.

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
#include<iostream>
#include<stack>
#include<vector>
using namespace std;
stack<int> stk;
int map[101][101];
int d[1025]; //0~3방향, 0~10세대
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
 
    for (int i = 1; i <= 10; i++) {
        for (int j = 0; j <= (1 << (i - 1)) - 1; j++) {
            stk.push(d[j]); //이전 세대의 것을 스택에 넣고
        }
        for (int j = 1 << (i - 1); j <= (1 << i) - 1; j++) {
            d[j] = (stk.top() + 1) % 4;
            stk.pop();
            //1씩 증가하면서 pop하면서 이전 세대의 것에 붙이면 현재 세대의 것이 나옴
        }
    }
 
    for (int i = 0; i < n; i++) {
        int x, y, dir, gen;
        cin >> x >> y >> dir >> gen;
        map[y][x] = 1;
        for (int j = 0; j <= (1 << gen) - 1; j++) {
            if ((d[j] + dir) % 4 == 0) {
                x++; //갱신하면서 움직여야 반영됨
                map[y][x] = 1;
            }
            else if ((d[j] + dir) % 4 == 1) {
                y--;
                map[y][x] = 1;
            }
            else if ((d[j] + dir) % 4 == 2) {
                x--;
                map[y][x] = 1;
            }
            else if ((d[j] + dir) % 4 == 3) {
                y++;
                map[y][x] = 1;
            }
        }
    }
    
    int cnt = 0;
    for (int i = 0; i < 100; i++) { //생각 없이 n까지만 잡으면 안 되고, x, y 최대 범위만큼
        for (int j = 0; j < 100; j++) { 
            if (map[i][j] == 1 && map[i][j + 1] == 1 &&
                map[i + 1][j] == 1 && map[i + 1][j + 1] == 1) cnt++;
        }
    }
    cout << cnt;
    return 0;
}
Colored by Color Scripter
cs

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

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

백준 15683번: 감시 (C++) (0)	2019.08.07
백준 14502번: 연구소 (C++) (0)	2019.08.07
백준 15686번: 치킨 배달 (C++) (0)	2019.08.05
백준 17141번: 연구소 2 (C++) (0)	2019.08.05
백준 11050번: 이항 계수1 (C++) (0)	2019.08.05

백준 15686번: 치킨 배달 (C++)

Hugxy 2019. 8. 5. 23:05

2019. 8. 5. 23:05

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

비교적 간단한 조합 / 백트래킹 / 전수조사 문제이다.

문제를 보면, 결국 모든 경우의 수를 조사해야 하는 상황이다. 따라서 집의 위치와, 치킨집의 위치를 따로 벡터에 담아주고,

백트래킹을 활용해서 치킨집을 m개 선택한 다음, 선택한 치킨집을 가지고 치킨 거리를 구하면 되겠다.

이 경우에 다시 일반 가정집을 검색할 필요가 없도록, 미리 초반에 일반집도 벡터에 담아두고 사용하면 되겠다.

[소스코드]

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
#include<iostream>
#include<vector>
#include<math.h>
#include<limits.h>

using namespace std;
int map[52][52], n, m, st = 0, arr[14];
 
vector<pair<int, int > > v, hv; //치킨집, 가정집
 
int res = INT_MAX;
bool isused[14];
void process() {//집마다 치킨집 여러개와의 거리가 있는데, 그 거리의 최소값의 합을 구한다
    int cityDis = 0;

    for (int i = 0; i < hv.size(); i++) {
        int Min = INT_MAX;
        for (int j = 0; j < m; j++) {
            int sumR = 0, sumC = 0;
            sumR += abs(hv[i].first - v[arr[j]].first);
            sumC += abs(hv[i].second - v[arr[j]].second);
            if (sumR + sumC < Min) Min = sumR + sumC;
        }
        cityDis += Min; //도시의 치킨거리
    }

    if (res > cityDis) res = cityDis; //도시의 치킨거리 최댓값 갱신 
}

void backTracking(int k) { //조합 템플릿
    if (k == m) {
        //arr에 치킨벡터 인덱스
        process();
        return;
    }

    if (k == 0) st = 0;
    for (int i = st; i < v.size(); i++) {
        if (!isused[i]) {
            arr[k] = i;
            st = i;
            isused[i] = true;
            backTracking(k + 1);
            isused[i] = false;
        }
    }
}

int main(void) {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> map[i][j];
            if (map[i][j] == 2) v.push_back({ i, j }); //치킨집
            else if (map[i][j] == 1) hv.push_back({ i, j }); //가정집
        }
    }
    
    backTracking(0);
 
    cout << res << '\n';
    return 0;
}
Colored by Color Scripter
cs

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

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

백준 14502번: 연구소 (C++) (0)	2019.08.07
백준 15685번: 드래곤 커브 (C++) (0)	2019.08.06
백준 17141번: 연구소 2 (C++) (0)	2019.08.05
백준 11050번: 이항 계수1 (C++) (0)	2019.08.05
백준 17142번: 연구소 3 (C++) (0)	2019.08.05

백준 17141번: 연구소 2 (C++)

Hugxy 2019. 8. 5. 22:07

2019. 8. 5. 22:07

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

연구소 3을 해결했다면 거저 먹을 수 있는 문제이다.

기본적으로 바이러스의 후보지들을 가지고 조합을 구해야 한다.

바이러스 후보지가 5곳이고 m = 3으로 주어진다면, 5Cm만큼의 경우의 수를 확인해보면 답을 찾을 수 있다.

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
#include<iostream>
#include<vector>
#include<queue>
#include<limits.h>
using namespace std;
int map[51][51], n, m, dis[51][51], st = 0, arr[11];
vector<pair<int, int> > v;
bool isused[11];
queue<pair<int, int> >q;
int dr[4] = { 0,0,1,-1 };
int dc[4] = { 1,-1,0,0 };
int res = INT_MAX;
 
void init() {
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            dis[i][j] = -1;
}
 
pair<bool, int> check() {
    int Max = -2;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (dis[i][j] == -1 && map[i][j] == 0) return { false, -2 };
            if (Max < dis[i][j]) Max = dis[i][j];
        }
    }
    return { true, Max }; //바이러스가 완전히 확산된 경우만 시간 반환
}
 
void bfs() {
    while (!q.empty()) {
        pair<int, int> cur = q.front();
        q.pop();
        for (int i = 0; i < 4; i++) {
            int nr = cur.first + dr[i];
            int nc = cur.second + dc[i];
            if (nr < 0 || nc < 0 || nr >= n || nr >= n) continue;
            if (map[nr][nc] == 1 || dis[nr][nc] >= 0) continue;
            q.push({ nr, nc });
            dis[nr][nc] = dis[cur.first][cur.second] + 1;
        }
    }
    if (check().first) {
        int rtn = check().second;
        if (rtn < res) res = rtn; //반환된 시간의 최솟값 갱신
    }
}
void backTracking(int k) {
    if (k == m) {
        for (int i = 0; i < m; i++) {
            //arr에 바이러스의 인덱스를 저장
            q.push({ v[arr[i]].first, v[arr[i]].second });
            dis[v[arr[i]].first][v[arr[i]].second]++;
        }
        bfs();
 
        init(); //dis 초기화
        
        return;
    }
    if (k == 0) st = 0; //조합 템플릿
    for (int i = st; i < v.size(); i++) {
        if (!isused[i]) {
            arr[k] = i;
            isused[i] = true;
            st = i;
            backTracking(k + 1);
            isused[i] = false;
        }
    }
}
int main(void) {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> map[i][j];
            if (map[i][j] == 2) v.push_back({ i, j });
        }
    }
    init();
 
    backTracking(0);
 
    if (res != INT_MAX) cout << res; //결과가 갱신된적이 없다면 제대로 확산된 적이 없는 것
    else
        cout << -1;
    return 0;
}
Colored by Color Scripter
cs

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

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

백준 15685번: 드래곤 커브 (C++) (0)	2019.08.06
백준 15686번: 치킨 배달 (C++) (0)	2019.08.05
백준 11050번: 이항 계수1 (C++) (0)	2019.08.05
백준 17142번: 연구소 3 (C++) (0)	2019.08.05
백준 17143번: 낚시왕 (C++) (0)	2019.08.04

백준 11050번: 이항 계수1 (C++)

Hugxy 2019. 8. 5. 12:48

2019. 8. 5. 12:48

문제 링크: https://www.acmicpc.net/problem/11050

n과 k가 주어질 때, nCk를 구하면 되는 문제이다.

팩토리얼 계산을 통해서 구현하면 된다.

팩토리얼을 통한 구현은, n이 15만 되더라도 int의 범위 근처이고, 21까지만 되도 long long의 범위 근처이기 때문에, 이 문제처럼 n이 10으로 작을 경우에만 사용한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<iostream>
using namespace std;
typedef long long ll;
int main(void) {
    ll n, k;
    cin >> n >> k;
    
    ll son = 1, mom = 1;
    for (int i = 0; i < k; i++) 
        son = son * (n - i);
 
    for (int i = 0; i < k; i++) 
        mom = mom * (k - i);
 
    cout << son / mom;
    return 0;
}
cs

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

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

백준 15686번: 치킨 배달 (C++) (0)	2019.08.05
백준 17141번: 연구소 2 (C++) (0)	2019.08.05
백준 17142번: 연구소 3 (C++) (0)	2019.08.05
백준 17143번: 낚시왕 (C++) (0)	2019.08.04
백준 16235번: 나무 재테크 (C++) (0)	2019.07.30

백준 17142번: 연구소 3 (C++)

Hugxy 2019. 8. 5. 02:24

2019. 8. 5. 02:24

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

17142번: 연구소 3

인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고, 활성 상태인 바이러스는 상하좌우로 인접한 모든 빈 칸으로 동시에 복제되며, 1초가 걸린다. 승원이는 연구소의 바이러스 M개를 활성 상태로 변경하려고 한다. 연구소는 크기가 N×N인 정사각형으로 나타낼 수 있으며, 정사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는

www.acmicpc.net

문제 설명

1. 비활성 바이러스의 위치가 여러곳 주어진다.

2. 그 중에서 M개를 선택해서 확산 바이러스로 만들고, 바이러스의 확산을 시작한다.

(확산 바이러스는 비활성 바이러스를 만나면 그 비활성 바이러스를 확산 바이러스로 바꾼다)

3. 바이러스가 전부 퍼질 때까지 걸린 시간의 최솟값을 구하여라.

문제를 시작하기 전에 몇가지 표현을 잘 이해하고 들어가야한다.

먼저 문제가 구하라고 한 것은, 바이러스가 다 퍼질 때까지 걸린 최소 시간이다. 퍼지는 바이러스가 활성 바이러스여야 한다는 말은 없다.

테스트케이스를 좋게 주지 않았더라면 괴랄한 정답률을 보여주지 않았을까 생각한다.

아래쪽에 있는 테스트 케이스를 활용하면 대부분의 엣지 케이스에 대한 감을 잡을 수 있을 것이다.

[알고리즘]

1. 백트레킹을 활용해서 전체 바이러스 중에서 m개를 선택한다.

2. 선택한 m개의 바이러스를 큐에 넣고 BFS를 돌린다.

3. 빈칸과 비활성 바이러스가 있으면서 방문하지 않은 지점이면 바이러스를 확산시키고, 시간을 기록한다.

4. 시간이 얼마 걸렸는지 파악하기 위해 방문처리 배열 내에서 최댓값을 찾는다. 이 때 최댓값을 선택할 때 그 지점이 바이러스가 위치하고 있는 지점이라면 최댓값으로 보지 않는다.

마지막 테스트 케이스에서와 같이, 이미 바이러스로 채워져있는 곳은 사실 방문할 필요가 없었던 지점이다. 하지만 거쳐가면서 확산이 이루어져야 하기 때문에 일단 채택은 하고, 바이러스가 전체로 퍼지는 시간에는 영향을 끼치면 안되기 때문에 제외해준다.

5. 위에서 구한 최댓값(시간)의 최솟값을 답으로 정한다.

#include<iostream>
#include<vector>
#include<queue>
#include<limits.h>
using namespace std;

int n, m, map[51][51], dis[51][51], arr[11], st = 0; //연구소 크기, 바이러스 개수
bool isused[11];
struct VIRUS {
	int r;
	int c;
};
vector<VIRUS> v;
queue<pair<int, int> > q;
int dr[4] = { 0,0,1,-1 };
int dc[4] = { 1,-1,0,0 };
int res = INT_MAX;

void bfs() {
	
	while (!q.empty()) {
		pair<int, int> cur = q.front();
		q.pop();
		
		for (int i = 0; i < 4; i++) {
			int nr = cur.first + dr[i];
			int nc = cur.second + dc[i];
			if (nr < 0 || nc < 0 || nr >= n || nc >= n) continue;
			if (dis[nr][nc] >= 0 || map[nr][nc] == 1) continue;
			
			q.push({ nr, nc });
			dis[nr][nc] = dis[cur.first][cur.second] + 1;
		}
	}
}
void init() {
	for(int i = 0 ; i < n ; i++)
		for (int j = 0; j < n; j++) 
			dis[i][j] = -1;
}
bool isDone(){
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (dis[i][j] == -1 && map[i][j] != 1)
				return false;
		}
	}
	return true;
}
void findMax() {
	int Max = 0;
	for (int i = 0; i < n; i++) 
		for (int j = 0; j < n; j++) 
			if (Max < dis[i][j] && map[i][j] != 2) 
				Max = dis[i][j];

	if (res > Max) res = Max;
}
void func(int k) {
	if (k == m) {

		for (int i = 0; i < m; i++) {
			int r = v[arr[i]].r;
			int c = v[arr[i]].c;
			q.push({ r, c });
			dis[r][c]++;
		}
		bfs();

		if (isDone()) 
			findMax();
		
		init();

		return;
	}

	if (k == 0) st = 0;
	for (int i = st; i < v.size(); i++) {
		if (!isused[i]) {
			arr[k] = i;
			st = i;
			isused[i] = true;
			func(k + 1);
			isused[i] = false;
		}
	}
}
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++) {
			cin >> map[i][j];
			dis[i][j] = -1;
			if (map[i][j] == 2) { //바이러스 위치 저장
				VIRUS tmp;
				tmp.r = i;
				tmp.c = j;
				v.push_back(tmp);
			}
		}

	func(0);

	if (res == INT_MAX) cout << -1 << '\n';
	else
		cout << res;
	return 0;
}

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

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

백준 17141번: 연구소 2 (C++) (0)	2019.08.05
백준 11050번: 이항 계수1 (C++) (0)	2019.08.05
백준 17143번: 낚시왕 (C++) (0)	2019.08.04
백준 16235번: 나무 재테크 (C++) (0)	2019.07.30
백준 16234번: 인구 이동 (C++) (0)	2019.07.26

PREV 이전 1 ···12 13 14 15 16 17 18 ···22 NEXT 다음

기록을