https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpLlKAQ4DFAUq

 

SW Expert Academy

SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

www.swexpertacademy.com

BFS를 이용하고 터널 구조물 타입에 따라서 하나하나 조건을 처리해줬다.

 

 

예를 들어 1번 터널 구조물의 경우에는

위쪽 방향에 있으면 이동할 수 있는 터널은 1, 2, 5, 6번

아래쪽 방향에 있으면 이동할 수 있는 터널은 1, 2, 4, 7번

왼쪽은 1, 3, 4, 5번, 오른쪽은 1, 3, 6, 7번이다.

 

이런 식으로 각 터널 구조물마다 이동할 수 있는 각 방향에 올 수 있는 터널이 있을 때 큐에 넣어서 이동할 수 있도록해줬다. 다른 사람들의 풀이를 보면 훨씬 깔끔하게 구현하신 분들이 많긴 하다... 나중에 다시 찾아보고 공부해봐야겠다.

 

 

BFS는 입력 받은 l시간만큼만 진행하기 위해 큐 사이즈만큼씩 진행했다.

(큐 사이즈만큼 이 각 단계(시간) 이므로)

 

 

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
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
 
int ans;
int n, m, r, c, l;
int map[50][50];
bool check[50][50];
 
int dx[] = { -1, 0, 1, 0 };
int dy[] = { 0, 1, 0, -1 };
 
void solve() {
    int time = 1;
    queue<pair<int, int>> q;
    q.push(make_pair(r, c));
    check[r][c] = true;
 
    int qsize;
    int cnt = 1;
    while (!q.empty()) {
        qsize = q.size();
        if (time == l) break;
        time++;
 
        while (qsize-- > 0) {
            int x = q.front().first;
            int y = q.front().second;
            q.pop();
 
            int nx, ny;
            if (map[x][y] == 1) {
 
                for (int k = 0; k < 4; k++) {
                    nx = x + dx[k];
                    ny = y + dy[k];
                    if (nx < 0 || ny < 0 || nx >= n || ny >m) continue;
                    if (check[nx][ny]) continue;
                    if (map[nx][ny] == 0) continue;
 
                    if (k == 0) {
                        if (map[nx][ny] == 1 || map[nx][ny] == 2 || map[nx][ny] == 5 || map[nx][ny] == 6) {
                            q.push(make_pair(nx, ny));
                            check[nx][ny] = true;
                            cnt++;
                        }
                    }
                    else if (k == 1) {
                        if (map[nx][ny] == 1 || map[nx][ny] == 3 || map[nx][ny] == 6 || map[nx][ny] == 7) {
                            q.push(make_pair(nx, ny));
                            check[nx][ny] = true;
                            cnt++;
                        }
                    }
                    else if (k == 2) {
                        if (map[nx][ny] == 1 || map[nx][ny] == 2 || map[nx][ny] == 4 || map[nx][ny] == 7) {
                            q.push(make_pair(nx, ny));
                            check[nx][ny] = true;
                            cnt++;
                        }
                    }
                    else {
                        if (map[nx][ny] == 1 || map[nx][ny] == 3 || map[nx][ny] == 4 || map[nx][ny] == 5) {
                            q.push(make_pair(nx, ny));
                            check[nx][ny] = true;
                            cnt++;
                        }
                    }
                }
 
            }
            else if (map[x][y] == 2) {
                nx = x + dx[0];
                ny = y + dy[0];
                if (nx >= 0 && ny >= 0 && nx < n && ny < m) {
                    if (!check[nx][ny]) {
                        if (map[nx][ny] == 1 || map[nx][ny] == 2 || map[nx][ny] == 5 || map[nx][ny] == 6) {
                            q.push(make_pair(nx, ny));
                            check[nx][ny] = true;
                            cnt++;
                        }
                    }
                }
 
                nx = x + dx[2];
                ny = y + dy[2];
                if (nx >= 0 && ny >= 0 && nx < n && ny < m) {
                    if (!check[nx][ny]) {
                        if (map[nx][ny] == 1 || map[nx][ny] == 2 || map[nx][ny] == 4 || map[nx][ny] == 7) {
                            q.push(make_pair(nx, ny));
                            check[nx][ny] = true;
                            cnt++;
                        }
                    }
                }
 
 
            }
            else if (map[x][y] == 3) {
                nx = x + dx[1];
                ny = y + dy[1];
                if (nx >= 0 && ny >= 0 && nx < n && ny < m) {
                    if (!check[nx][ny]) {
                        if (map[nx][ny] == 1 || map[nx][ny] == 3 || map[nx][ny] == 6 || map[nx][ny] == 7) {
                            q.push(make_pair(nx, ny));
                            check[nx][ny] = true;
                            cnt++;
                        }
 
                    }
                }
 
                nx = x + dx[3];
                ny = y + dy[3];
                if (nx >= 0 && ny >= 0 && nx < n && ny < m) {
                    if (!check[nx][ny]) {
                        if (map[nx][ny] == 1 || map[nx][ny] == 3 || map[nx][ny] == 4 || map[nx][ny] == 5) {
                            q.push(make_pair(nx, ny));
                            check[nx][ny] = true;
                            cnt++;
                        }
 
                    }
                }
            }
            else if (map[x][y] == 4)
            {
                for (int k = 0; k < 2; k++) {
                    nx = x + dx[k];
                    ny = y + dy[k];
                    if (nx < 0 || ny < 0 || nx >= n || ny >m) continue;
                    if (check[nx][ny]) continue;
                    if (map[nx][ny] == 0) continue;
 
                    if (k == 0) {
                        if (map[nx][ny] == 1 || map[nx][ny] == 2 || map[nx][ny] == 5 || map[nx][ny] == 6) {
                            q.push(make_pair(nx, ny));
                            check[nx][ny] = true;
                            cnt++;
                        }
                    }
                    else if (k == 1) {
                        if (map[nx][ny] == 1 || map[nx][ny] == 3 || map[nx][ny] == 6 || map[nx][ny] == 7) {
                            q.push(make_pair(nx, ny));
                            check[nx][ny] = true;
                            cnt++;
                        }
                    }
                }
 
 
            }
            else if (map[x][y] == 5) {
                for (int k = 1; k < 3; k++) {
                    nx = x + dx[k];
                    ny = y + dy[k];
                    if (nx < 0 || ny < 0 || nx >= n || ny >m) continue;
                    if (check[nx][ny]) continue;
                    if (map[nx][ny] == 0) continue;
 
                    if (k == 1) {
                        if (map[nx][ny] == 1 || map[nx][ny] == 3 || map[nx][ny] == 6 || map[nx][ny] == 7) {
                            q.push(make_pair(nx, ny));
                            check[nx][ny] = true;
                            cnt++;
                        }
                    }
                    else if (k == 2) {
                        if (map[nx][ny] == 1 || map[nx][ny] == 2 || map[nx][ny] == 4 || map[nx][ny] == 7) {
                            q.push(make_pair(nx, ny));
                            check[nx][ny] = true;
                            cnt++;
                        }
                    }
                }
            }
            else if (map[x][y] == 6) {
                for (int k = 2; k < 4; k++) {
                    nx = x + dx[k];
                    ny = y + dy[k];
                    if (nx < 0 || ny < 0 || nx >= n || ny >m) continue;
                    if (check[nx][ny]) continue;
                    if (map[nx][ny] == 0) continue;
 
                    if (k == 2) {
                        if (map[nx][ny] == 1 || map[nx][ny] == 2 || map[nx][ny] == 4 || map[nx][ny] == 7) {
                            q.push(make_pair(nx, ny));
                            check[nx][ny] = true;
                            cnt++;
                        }
                    }
                    else {
                        if (map[nx][ny] == 1 || map[nx][ny] == 3 || map[nx][ny] == 4 || map[nx][ny] == 5) {
                            q.push(make_pair(nx, ny));
                            check[nx][ny] = true;
                            cnt++;
                        }
                    }
                }
            }
            else if (map[x][y] == 7) {
                for (int k = 0; k < 4; k += 3) {
                    nx = x + dx[k];
                    ny = y + dy[k];
                    if (nx < 0 || ny < 0 || nx >= n || ny >m) continue;
                    if (check[nx][ny]) continue;
                    if (map[nx][ny] == 0) continue;
 
 
                    if (k == 0) {
                        if (map[nx][ny] == 1 || map[nx][ny] == 2 || map[nx][ny] == 5 || map[nx][ny] == 6) {
                            q.push(make_pair(nx, ny));
                            check[nx][ny] = true;
                            cnt++;
                        }
                    }
                    else {
                        if (map[nx][ny] == 1 || map[nx][ny] == 3 || map[nx][ny] == 4 || map[nx][ny] == 5) {
                            q.push(make_pair(nx, ny));
                            check[nx][ny] = true;
                            cnt++;
                        }
                    }
                }
            }
 
        }
    }
 
 
    ans = cnt;
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie();
 
    int T;
    cin >> T;
    for (int tc = 1; tc <= T; tc++) {
        ans = 0;
        memset(check, false, sizeof(check));
        cin >> n >> m >> r >> c >> l;
 
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                cin >> map[i][j];
            }
        }
 
        solve();
 
        cout << '#' << tc << ' ' << ans << "\n";
 
    }
 
    return 0;
}
Colored by Color Scripter
  
저작자표시

'SWEA > 모의 SW 역량테스트(C++)' 카테고리의 다른 글

[SWEA] 2382. [모의 SW 역량테스트] 미생물 격리  (0) 2019.08.08
[SWEA] 5650. [모의 SW 역량테스트] 핀볼 게임  (0) 2019.08.07
[SWEA] 5644. [모의 SW 역량테스트] 무선 충전  (0) 2019.08.07
[SWEA] 2112. [모의 SW 역량테스트] 보호 필름  (0) 2019.08.07
[SWEA] 5656. [모의 SW 역량테스트] 벽돌 깨기  (0) 2019.08.06

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRDL1aeugDFAUo

 

SW Expert Academy

SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

www.swexpertacademy.com

이 문제는 일단 행과 열이 반대로 되어 있으므로 주의해야 한다.

나는 그냥 x좌표와 y좌표를 입력받아서 반대로 저장해줬다.

그리고 BC는 BC의 좌표와 충전 범위(c), 성능(p)의 정보를 가지고 있기 때문에 구조체로 만들어서 벡터에 저장해줬다.

 

 

이제 입력받은 시간 정보에 따라서 사용자들을 각각 이동시킬 건데 매시간마다 A와 B의 최대 충전량을 구해서 정답에 더해준다. 이때 주의할 점은 이동 정보는 m개이지만 0초일 때도 계산해줘야 하므로 총 m+1번 계산을 해줘야 한다.

 

 

충전량의 최댓값을 계산해줄 때는 사용자 A와 B 각각 접속할 수 있는 모든 BC의 성능을 배열에 저장해놓고

A와 B가 모든 BC를 접속해보는 경우를 모두 구해준다.

여기서 또 주의할 점은 같은 BC에 접속하는 경우이다.

문제 조건에 따라 같은 BC에 접속할 경우 성능을 분배해줘야 한다.

근데 같은 BC를 사용하는 경우를 구할 때, 한쪽의 성능이 0인 경우(해당 BC에 접속할 수 없는 경우)는 반으로 나눠주면 안 되기 때문에 주의해야 한다.

 

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
#include <iostream>
#include <vector>
#include <cmath>
#include <cstring>
using namespace std;
 
int m, a, ans;
int userA[101];
int userB[101];
 
int dx[] = { 0,-1,0,1,0 };
int dy[] = { 0,0,1,0,-1 };
 
 
struct BC {
    int x;
    int y;
    int c;
    int p;
    BC(int x, int y, int c, int p) : x(x), y(y), c(c), p(p) {}
};
 
vector<BC> bclist;
 
 
int calc(int ax, int ay, int bx, int by) {
 
    //사용자 A의 BC별 충전량
    int sumA[8];
    //사용자 B의 BC별 충전량
    int sumB[8];
 
    memset(sumA, 0, sizeof(sumA));
    memset(sumB, 0, sizeof(sumB));
 
    int d;
    //사용자 A로부터 각 BC의 위치를 계산하여 i번 BC에 접속할 수 있다면 sumA[i]에 충전량을 저장한다.
    for (int i = 0; i < a; i++) {
        int bcx = bclist[i].x;
        int bcy = bclist[i].y;
        int c = bclist[i].c;
        int p = bclist[i].p;
 
        d = abs(ax - bcx) + abs(ay - bcy);
        if (d <= c) {
            sumA[i] = p;
        }
    }
 
    //사용자 B로부터 각 BC의 위치를 계산하여 i번 BC에 접속할 수 있다면 sumB[i]에 충전량을 저장한다.
    for (int i = 0; i < a; i++) {
        int bcx = bclist[i].x;
        int bcy = bclist[i].y;
        int c = bclist[i].c;
        int p = bclist[i].p;
 
        d = abs(bx - bcx) + abs(by - bcy);
        if (d <= c) {
            sumB[i] = p;
        }
    }
 
 
    //사용자 A와 사용자 B의 가능한 충전량의 합 중 최댓값을 sum에 저장
    int sum = 0;
    for (int i = 0; i < a; i++) {
        for (int j = 0; j < a; j++) {
            int tmp = sumA[i] + sumB[j];
 
            //둘다 같은 BC에 접속할 수 있는 상태에서, 같은 BC에 접속한 경우 충전 양은 반으로 나눠진다.
            //(i == j) 이지만 한 명이 접속할 수 없는 상태(sum배열의 값이 0)인 경우 반으로 나누면 안된다.
            if (i == j && sumA[i] != 0 && sumB[i] != 0) tmp /= 2;
 
            if (sum < tmp) sum = tmp;
        }
    }
 
 
    return sum;
}
 
 
void solve() {
 
    //사용자 A의 초기 위치
    int ax = 0, ay = 0;
    //사용자 B의 초기 위치
    int bx = 9, by = 9;
 
 
    //m시간만큼 이동
    for (int t = 0; t < m; t++) {
 
        //현재시간에서 이용할수 있는 최대 충전 양을 구해서 ans에 더허ㅐ준다.
        ans += calc(ax, ay, bx, by);
 
        //이동
        ax += dx[userA[t]];
        ay += dy[userA[t]];
        bx += dx[userB[t]];
        by += dy[userB[t]];
 
    }
 
    //m시간에 이동한 위치에서 다시 한번 계산해준다.
    ans += calc(ax, ay, bx, by);
 
 
 
}
 
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie();
 
    int T;
    cin >> T;
    for (int tc = 1; tc <= T; tc++) {
        ans = 0;
        bclist.clear();
 
        cin >> m >> a;
 
        //사용자 이동 정보
        for (int i = 0; i < m; i++) {
            cin >> userA[i];
        }
        for (int i = 0; i < m; i++) {
            cin >> userB[i];
        }
 
 
        //BC정보
        int x, y, c, p;
        for (int i = 0; i < a; i++) {
            cin >> x >> y >> c >> p;
            x--;
            y--;
            bclist.push_back(BC(y, x, c, p)); //행과 열 반대로 넣어줌!
        }
 
 
        solve();
 
 
        cout << '#' << tc << ' ' << ans << "\n";
 
    }
 
    return 0;
}
Colored by Color Scripter
  
저작자표시

'SWEA > 모의 SW 역량테스트(C++)' 카테고리의 다른 글

[SWEA] 5650. [모의 SW 역량테스트] 핀볼 게임  (0) 2019.08.07
[SWEA] 1953. [모의 SW 역량테스트] 탈주범 검거  (0) 2019.08.07
[SWEA] 2112. [모의 SW 역량테스트] 보호 필름  (0) 2019.08.07
[SWEA] 5656. [모의 SW 역량테스트] 벽돌 깨기  (0) 2019.08.06
[SWEA] 1949. [모의 SW 역량테스트] 등산로 조성  (0) 2019.08.06

https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V1SYKAaUDFAWu

 

SW Expert Academy

SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

www.swexpertacademy.com

모든 막(가로 방향)에 약품을 넣지 않는 경우/ A약품을 투입하는 경우/ B약품을 투입하는 경우를 구해주면 된다.

이미 합격기준을 통과한 최소 개수가 있는 경우, 해당 최소 개수보다 더 큰 경우는 탐색하지 않는다. 즉 약품을 더 투입하는 경우를 구하지 않으면서 탐색 시간을 줄일 수 있다.

 

성능 검사를 할 때는 모든 세로를 검사해주면 되는데

k개만큼의 연속된 같은 셀이 존재한다면 해당 열은 통과이고 이렇게 모든 열이 통과해야 한다.

 

나는 밑의 코드에서 bool변수 두 개를 적당히 활용하여 구현하였다.

먼저 flag 하나를 처음에 true로 두고 연속된 k개가 같지 않다면 false로 바꾸고 한 칸 내려와서 다시 k개만큼을 비교한다.

만약에 k개만큼 같았다면(합격 기준을 통과했다면) flag가 그대로 true인 상태이므로 해당 열은 통과이고 다음 열 검사로 넘어간다.

 

그리고 각 열이 통과했는지 확인해줄 bool 변수 colok를 처음에 false로 두고, 위에서 flag가 true가 됐을 때 같이 true가 되도록 해줬다.

해당 열의 검사가 끝났는데 colok가 false라면 해당 열은 통과를 하지 못했으므로 전체 검사도 통과하지 못하므로 바로 false를 리턴한다.

사실 변수 하나만 써도 적당히 잘 구현할 수 있긴 하다.

 

그리고 이 문제에서 실수할 수 있는 부분은 k가 1인 경우이다.

k가 1인 경우는 합격기준이 1이기 때문에 1개만 연속적으로 같으면 되므로 무조건 합격기준을 통과한다.

이 경우에는 바로 0을 출력해주고 다음 테스트 케이스로 넘어간다.

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
#include <iostream>
#include <cstring>
using namespace std;
 
int ans;
int d, w, k;
 
 
bool check(int film[13][20]) {
    
    //모든 세로를 검사
    for (int j = 0; j < w; j++) {
        
        //j번열에 연속된 k개의 같은 셀이 있는지 검사
        bool colok = false;
        for (int i = 0; i <= d - k; i++) {
            
            bool flag = true;
            for (int l = i+1; l < i + k; l++) {
                if (film[i][j] != film[l][j]) {
                    flag = false;
                    break;
                }
            }
 
            //한번이라도 연속되는 k개의 같은 셀이 있다면 현재 열은 통과이다
            if (flag) {
                colok = true;
                break;
            }
        }
 
        //열이 하나라도 통과를 하지 못하면 바로 false를 리턴
        if (!colok) {
            return false;
        }
    }
 
    //위에서 false를 리턴하지 않았다면 검사를 통과한 것이다
    return true;
}
 
void mapcopy(int film[13][20], int newfilm[13][20]) {
    for (int i = 0; i < d; i++) {
        for (int j = 0; j < w; j++) {
            newfilm[i][j] = film[i][j];
        }
    }
}
 
void solve(int cnt, int index, int film[13][20]) {
    //현재 사용한 개수가 이미 최솟값(정답)보다 같거나 크다면 더 검사하지 않는다.
    if (cnt >= ans) return;
    //현재 상태에서 성능을 검사한다
    if (check(film)) {
        //성능 검사를 통과했다면 ans에 cnt를 저장
        ans = cnt;
        return;
    }
    //모든 막에 약품을 투입하는 경우를 구해줬다.
    if (index == d) return;
 
    int newfilm[13][20];
    mapcopy(film, newfilm);
 
 
    //index번째 막에 약품을 투입하지 않는다.
    solve(cnt, index + 1, newfilm);
 
 
    //index번째 막에 A약품을 투입한다.
    for (int j = 0; j < w; j++) {
        newfilm[index][j] = 0;
    }
    solve(cnt + 1, index + 1, newfilm);
 
 
    //index번째 막에 B약품을 투입한다.
    for (int j = 0; j < w; j++) {
        newfilm[index][j] = 1;
    }
    solve(cnt + 1, index + 1, newfilm);
 
}
 
 
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int T;
    cin >> T;
    for (int tc = 1; tc <= T; tc++) {
        ans = 20;
        cin >> d >> w >> k;
 
        int film[13][20];
        for (int i = 0; i < d; i++) {
            for (int j = 0; j < w; j++) {
                cin >> film[i][j];
            }
        }
 
        //합격기준이 1인 경우에는 무조건 통과이므로 다음 테스트 케이스로 넘어간다
        if (k == 1) {
            cout << '#' << tc << ' ' << 0 << '\n';
            continue;
        }
        
        solve(0,0, film);
        cout << '#' << tc << ' ' << ans << '\n';
    
        
    }
 
 
 
    return 0;
}
Colored by Color Scripter
  
저작자표시

'SWEA > 모의 SW 역량테스트(C++)' 카테고리의 다른 글

[SWEA] 1953. [모의 SW 역량테스트] 탈주범 검거  (0) 2019.08.07
[SWEA] 5644. [모의 SW 역량테스트] 무선 충전  (0) 2019.08.07
[SWEA] 5656. [모의 SW 역량테스트] 벽돌 깨기  (0) 2019.08.06
[SWEA] 1949. [모의 SW 역량테스트] 등산로 조성  (0) 2019.08.06
[SWEA] 4014. [모의 SW 역량테스트] 활주로 건설  (0) 2019.08.06

https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRQm6qfL0DFAUo

 

SW Expert Academy

SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

www.swexpertacademy.com

구슬을 쏠 수 있는 n번을 모든 열에서 쏴보면 된다.

처음에 구슬을 쏘는 순서를 다 정해준다음에 순서에 맞게 구슬을 쏘다가 시간 초과가 났다. 왜냐하면

대충 1 번열, 2 번열, 3번열의 순서로 쏘는 경우와 1번열, 2번열 4 번열의 순서로 쏘는 경우가 있다고 했을 때 매번 1 번열과 2 번열을 깼을 때의 상태를 다시 구하기 때문이다.

 

 

그래서 1번 쏜 결과로부터 다음번 쏘는 결과를 바로바로 구해주도록 했다.

예를 들어, 2번 열에서 구슬을 쐈다고 했을 때, 깨져있는 상태에서 바로 다음 구슬을 쏘는 경우를 구해줘야 시간을 줄일 수 있다.

그리고 보내줄 때마다 물론 새로 배열을 만들어서 보내줘야 한다. (어느 열에서 쏘냐에 따라 현재 상태로부터 각각 다른 상태가 되기 때문)

 

 

벽을 부술 때는 1보다 큰 벽돌들을 계속 큐에 넣어 연쇄적으로 깨지도록 했다.

벽을 연쇄적으로 쭉 깨뜨렸으면 이제 벽돌들이 떨어지는 걸 구현해줘야 하는데

모든 열을 검사하며 맨 밑 에칸부터 시작해서 빈칸을 찾는다. 빈칸이 있다면 그 위칸부터 다시 벽돌을 찾아서 내려준다.

이때, 위쪽이 계속 빈칸이라면(떠있는 벽돌이 없다면) flag를 활용하여 다음 열 검사로 넘어간다.

 

 

구슬을 n번만큼 모두 쐈다면 남은 벽돌의 개수를 구해주고 정답 변수에 최솟값을 저장해준다.

내가 구현한 코드는 처음에 다 깨져있는 상태인 경우(모두 0인 상태)에 아예 남은 벽돌을 검사하지 않아서

(밑의 코드 131번 줄에서 계속 continue 된다)

ans가 초기값인 경우에는 0을 출력하도록 했다.

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
#include <iostream>
#include <queue>
using namespace std;
 
 
int n, w, h, ans;
 
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
 
int count(int newmap[15][12]) {
    int cnt = 0;
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
 
            //0이 아닌 칸(벽돌이 남아있는 칸)을 계산
            if (newmap[i][j] != 0) cnt++;
        }
    }
 
    return cnt;
}
 
 
//벽돌 밑으로 떨어진다.
void move(int newmap[15][12]) {
    //모든 열을 검사
    for (int j = 0; j < w; j++) {
        bool flag = false;
        for (int i = h - 1; i >= 0; i--) {
            if (newmap[i][j] != 0) continue;
 
            //빈칸을 찾았으면 다시 위쪽에 떠 있는 벽돌을 찾아준다.
            for (int k = i - 1; k >= 0; k--) {
                if (newmap[k][j] == 0) continue;
 
                newmap[i][j] = newmap[k][j];
                newmap[k][j] = 0;
                flag = true;
                break;
            }
 
            //위에 떠있는 벽돌이 없으므로 다음열을 검사해주면 된다.
            if (!flag) break;
 
        }
    }
}
 
//벽돌을 부순다.
void go(int x, int y, int newmap[15][12]) {
 
    queue<pair<int, int>> q;
    q.push(make_pair(x, y));
    int num;
    while (!q.empty()) {
        x = q.front().first;
        y = q.front().second;
        q.pop();
        num = newmap[x][y];
 
        newmap[x][y] = 0;
 
        if (num == 1) continue;
 
        //네방향으로 num-1번만큼 벽돌 제거, 1보다 크면 큐에 추가
        for (int k = 0; k < 4; k++) {
            int nx = x;
            int ny = y;
            for (int l = 0; l < num - 1; l++) {
                nx += dx[k];
                ny += dy[k];
                
                if (nx < 0 || ny < 0 || nx >= h || ny >= w) break;
 
                if (newmap[nx][ny] > 1) {
                    q.push(make_pair(nx, ny));
                }
                else {
                    newmap[nx][ny] = 0;
                }
 
            }
 
        }
    }
}
 
 
void mapcpy(int map[15][12], int newmap[15][12]) {
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            newmap[i][j] = map[i][j];
        }
    }
}
 
 
void solve(int index, int map[15][12]) {
    if (index == n) {
        int tmp = count(map);
        if (ans > tmp) ans = tmp;
 
        return;
    }
 
 
    int x, y;
    //모든 열에서 구슬을 쏘는 경우를 구한다.
    for (int col = 0; col < w; col++) {
        x = 0;
        y = col;
 
        //맨 위의 벽돌을 찾는다.
        while (true) {
            //이번 열이 다 깨져있다.
            if (x >= h) {
                break;
            }
 
            //맨 위 벽돌을 찾았다.
            if (map[x][y] != 0) {
                break;
            }
 
            //밑의 칸으로 이동
            x++;
        }
 
        //이번 열에 벽돌이 없으면 다음 선택한 열로 넘어간다.
        if (x == h) continue;
 
        int newmap[15][12];
        mapcpy(map, newmap);
 
        //구슬 쏜다.
        go(x, y, newmap);
 
        //벽돌 내려온다.
        move(newmap);
 
        solve(index + 1, newmap);
    }
 
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int T;
    cin >> T;
    for (int tc = 1; tc <= T; tc++) {
        cin >> n >> w >> h;
        ans = 200;
 
        int map[15][12];
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                cin >> map[i][j];
            }
        }
 
        solve(0,map);
 
        if (ans == 200) {
            //ans가 초기값인 경우에는 0을 출력(처음부터 다 깨져있는 경우)
            cout << '#' << tc << ' ' << 0 << '\n';
        }
        else {
            cout << '#' << tc << ' ' << ans << '\n';
        }
 
    }
 
 
    return 0;
}
Colored by Color Scripter
  
저작자표시

'SWEA > 모의 SW 역량테스트(C++)' 카테고리의 다른 글

[SWEA] 5644. [모의 SW 역량테스트] 무선 충전  (0) 2019.08.07
[SWEA] 2112. [모의 SW 역량테스트] 보호 필름  (0) 2019.08.07
[SWEA] 1949. [모의 SW 역량테스트] 등산로 조성  (0) 2019.08.06
[SWEA] 4014. [모의 SW 역량테스트] 활주로 건설  (0) 2019.08.06
[SWEA] 2115. [모의 SW 역량테스트] 벌꿀채취  (0) 2019.08.05

https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PoOKKAPIDFAUq

 

SW Expert Academy

SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

www.swexpertacademy.com

이 문제는 갈 수 있는 최대 길이를 구하는 문제이므로 dfs를 이용해서 풀 수 있다.

dfs의 depth가 문제의 최대 길이가 된다.

 

풀이

1. 입력받은 지형의 높이 중 가장 높은 높이를 저장해 놓는다.

 

2. 해당 높이를 가지고 있는 지형(가장 높은 봉우리)의 좌표를 벡터에 저장한다.

 

3. 가장 높은 봉우리로부터 출발할 수 있으므로 위에서 저장한 좌표에서 각각 출발해본다.

 

4. 출발할 때는, 모든 칸을 0번부터 k번까지 깎아보는 모든 경우에서 출발(dfs탐색)한다. 해당 칸을 깎은 경우에서 돌아온다면 깎은 만큼 다시 더해준다. (1칸만 깎을 수 있으므로)

 

5.dfs탐색을 할 때는 문제 조건에 따라 이동할 칸이 현재 지형보다 더 낮아야 이동할 수 있고, 다음 칸으로 이동할 때마다 길이를 하나씩 늘려준다.

 

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
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
 
int n, k, ans;
int map[8][8];
bool visit[8][8];
vector<pair<int, int>> toplist;
 
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
 
 
void dfs(int x, int y, int len) {
    //방문 체크
    visit[x][y] = true;
    //최대 길이를 저장
    if (ans < len) ans = len;
 
    //가로방향, 세로방향으로 이동
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
 
        //범위 체크
        if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
        //방문 체크
        if (visit[nx][ny]) continue;
        //같거나 높은지형으로는 갈 수 없다.
        if (map[nx][ny] >= map[x][y]) continue;
 
        //길이를 하나 늘린채로 (nx, ny)로 이동
        dfs(nx, ny, len+1);
 
        //탐색에서 돌아온 후에 방문체크를 지워준다.
        visit[nx][ny] = false;
    }
 
 
}
 
void solve() {
 
    int vsize = toplist.size();
    int x, y;
 
    //모든 가장 높은 봉우리
    for (int t = 0; t < vsize; t++) {
        x = toplist[t].first;
        y = toplist[t].second;
 
        //모든 칸을 0부터 k만큼 깎아본다.
        for (int l = 0; l <= k; l++) {
 
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    //현재 시작하는 봉우리인 경우 깎지 않는다.
                    if (i == x && y == j) continue;
 
                    //(i,j)칸을 l만큼 깎는다.
                    map[i][j] -= l;
                    //visit 배열 초기화 후에
                    memset(visit, false, sizeof(visit));
                    //dfs탐색
                    dfs(x,y, 1);
 
                    //탐색에서 돌아온 후 다시 l을 더해준다.
                    map[i][j] += l;
                }
            }
 
        }
 
 
    }
 
 
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int T;
    cin >> T;
    for (int tc = 1; tc <= T; tc++) {
        cin >> n >> k;
 
        int maxh = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                cin >> map[i][j];
                //봉우리의 최댓값을 저장
                if (maxh < map[i][j]) maxh = map[i][j];
            }
        }
 
        //새로운 테스트케이스를 위해서 초기화
        toplist.clear();
        ans = 0;
 
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                //가장 높은 봉우리들을 벡터에 넣는다.
                if (map[i][j] == maxh) toplist.push_back(make_pair(i, j));
            }
        }
 
        solve();
        
        cout << '#' << tc << ' ' << ans << '\n';
    }
 
    return 0;
}
Colored by Color Scripter
  
저작자표시

'SWEA > 모의 SW 역량테스트(C++)' 카테고리의 다른 글

[SWEA] 2112. [모의 SW 역량테스트] 보호 필름  (0) 2019.08.07
[SWEA] 5656. [모의 SW 역량테스트] 벽돌 깨기  (0) 2019.08.06
[SWEA] 4014. [모의 SW 역량테스트] 활주로 건설  (0) 2019.08.06
[SWEA] 2115. [모의 SW 역량테스트] 벌꿀채취  (0) 2019.08.05
[SWEA] 1952. [모의 SW 역량테스트] 수영장  (0) 2019.08.05

https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeW7FakkUDFAVH

 

SW Expert Academy

SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

www.swexpertacademy.com

나는 그냥 문제에 나와있는대로 하나하나 처리를 해줬는데 다른 사람들의 풀이를 보니까 더 간단하게 풀었던데 나중에 보고 다시 공부해봐야겠다.

 

먼저 가로방향과 세로방향을 각각 구해줬다.

가로 방향을 구할 때는 모든 행에 대해서 각각의 열을 비교하였다.

  1. j열과 j+1 의 높이가 같다면 다음 열의 비교로 넘어간다.
  2. 높이 차이가 1보다 크다면 경사로를 놓을 수도 없으므로 해당 행에는 활주로 건설이 불가능하다.
  3. 높이차이가 1이라면 경사로를 놓을 수 있는지 확인한다. 밑의 조건에 맞지 않는다면 flag를 false로 바꿔준다.
    1. 경사로의 길이 x만큼을 놓았을 때 범위를 넘어가지 않는지 확인.
    2. 경사로를 놓아줄 x만큼의 칸의 높이가 같은지 확인.
    3. 경사로를 놓을 자리에 이미 경사로가 놓여있지 않은지 확인.
  4. 위의 조건을 모두 통과하였다면 경사로를 놓아줄 것인데 j가 j+1보다 컸다면 j+1부터 뒷쪽으로 경사로를 놓아주면 되고, 반대의 경우에는 j부터 앞쪽으로 경사로를 놓아주면 된다.
  5.  
  6. 행의 열 끝까지가는 동안 flag가 true라면 (위의 조건에서 한번도 걸리지 않았다면) 해당 행은 활주로를 건설할 수 있다.

위와 같은 방식으로 세로 방향도 행과 열을 바꿔서 구해주면된다. 

 

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
#include <iostream>
#include <cstring>
using namespace std;
 
int n, x, ans;
int map[20][20];
bool checkG[20][20];
bool checkS[20][20];
 
int checkGaro() {
    int cnt = 0;
 
    //모든 행을 검사
    for (int i = 0; i < n; i++) {
 
        bool flag = true;
        for (int j = 0; j < n - 1; j++) {
            //높이가 같으면 다음 칸으로 넘어간다
            if (map[i][j] == map[i][j + 1]) continue;
 
 
            //높이 차이를 구해준다.
            int tmp = map[i][j] - map[i][j + 1];
            if (tmp < 0) tmp = -tmp;
 
            //1보다 차이가 크면 경사로를 놓을 수 없으므로 해당 행은 활주로 건설 불가
            if (tmp > 1) {
                flag = false;
                break;
            }
 
 
            //앞쪽이 더 높은 경우 뒷쪽에 경사로 놔준다.
            if (map[i][j] > map[i][j + 1]) {
                //범위를 벗어나는 경우
                if (j + x >= n) {
                    flag = false;
                    break;
                }
 
                //경사로를 x만큼 놓을 수 있는지 검사
                for (int k = j + 1; k < j + x; k++) {
                    //경사로를 놓을 자리의 높이가 같은지 검사
                    if (map[i][k] != map[i][k + 1]) {
                        flag = false;
                        break;
                    }
 
                }
 
                for (int k = j + 1; k < j + x + 1; k++) {
                    //경사로가 이미 놓여져있는지 검사
                    if (checkG[i][k]) {
                        flag = false;
                        break;
                    }
                }
 
 
                //검사를 통과했다면 경사로를 놓아준다.
                if (flag) {
                    for (int k = j + 1; k < j + 1 + x; k++) {
                        checkG[i][k] = true;
                    }
                }
 
 
            }
            else {//뒷칸이 더 큰 경우
                //범위를 벗어나는 경우
                if (j + 1 - x < 0) {
                    flag = false;
                    break;
                }
 
                //경사로를 x만큼 놓을 수 있는지 검사
                for (int k = j; k > j + 1 - x; k--) {
                    if (map[i][k] != map[i][k - 1]) {
                        flag = false;
                        break;
                    }
                }
 
                for (int k = j; k > j - x; k--) {
                    if (checkG[i][k]) {
                        flag = false;
                        break;
                    }
                }
 
                //검사를 통과했다면 경사로를 놓아준다.
                if (flag) {
                    for (int k = j; k > j - x - 1; k--) {
                        checkG[i][k] = true;
                    }
                }
 
            }
 
            //활주로를 건설할 수 없다.
            if (!flag) break;
 
        }
 
        //이번행은 활주로를 건설할 수 있다.
        if (flag) cnt++;
 
    }
 
 
    return cnt;
 
}
 
 
int checkSero() {
    int cnt = 0;
 
    //모든 열을 검사
    for (int j = 0; j < n; j++) {
 
        bool flag = true;
        for (int i = 0; i < n - 1; i++) {
 
            if (map[i][j] == map[i + 1][j]) continue;
 
 
            //높이 차이를 구해준다.
            int tmp = map[i][j] - map[i + 1][j];
            if (tmp < 0) tmp = -tmp;
 
            //1보다 차이가 크면 경사로를 놓을 수 없으므로 해당 행은 활주로 건설 불가
            if (tmp > 1) {
                flag = false;
                break;
            }
 
 
            //앞쪽이 더 높은 경우 뒷쪽에 경사로 놔준다.
            if (map[i][j] > map[i + 1][j]) {
                //범위를 벗어나는 경우
                if (i + x >= n) {
                    flag = false;
                    break;
                }
 
                //경사로를 x만큼 놓을 수 있는지 검사
                for (int k = i + 1; k < i + x; k++) {
                    //높이가 같은지 검사
                    if (map[k][j] != map[k + 1][j]) {
                        flag = false;
                        break;
                    }
 
                    
                }
 
                for (int k = i + 1; k < i + x + 1; k++) {
                    //이미 놓여져있는지 검사
                    if (checkS[k][j]) {
                        flag = false;
                        break;
                    }
                }
 
 
                //검사를 통과했다면 경사로를 놓아준다.
                if (flag) {
                    for (int k = i + 1; k < i + 1 + x; k++) {
                        checkS[k][j] = true;
                    }
                }
 
 
            }
            else {
                //범위를 벗어나는 경우
                if (i + 1 - x < 0) {
                    flag = false;
                    break;
                }
 
                //경사로를 x만큼 놓을 수 있는지 검사
                for (int k = i; k > i + 1 - x; k--) {
                    if (map[k][j] != map[k - 1][j]) {
                        flag = false;
                        break;
                    }
 
                    
                }
 
                for (int k = i; k > i - x; k--) {
                    if (checkS[k][j]) {
                        flag = false;
                        break;
                    }
                }
 
                //검사를 통과했다면 경사로를 놓아준다.
                if (flag) {
                    for (int k = i; k > i - x - 1; k--) {
                        checkS[k][j] = true;
                    }
                }
 
            }
 
            if (!flag) break;
 
        }
 
        if (flag) cnt++;
 
    }
 
 
    return cnt;
}
 
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int T;
    cin >> T;
    for (int tc = 1; tc <= T; tc++) {
        ans = 0;
        memset(checkG, false, sizeof(checkG));
        memset(checkS, false, sizeof(checkS));
 
        cin >> n >> x;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                cin >> map[i][j];
            }
        }
        
 
        ans = checkGaro() + checkSero();
        
        cout << '#' << tc << ' ' << ans << '\n';
    }
 
 
 
    return 0;
}
Colored by Color Scripter
  
저작자표시

'SWEA > 모의 SW 역량테스트(C++)' 카테고리의 다른 글

[SWEA] 5656. [모의 SW 역량테스트] 벽돌 깨기  (0) 2019.08.06
[SWEA] 1949. [모의 SW 역량테스트] 등산로 조성  (0) 2019.08.06
[SWEA] 2115. [모의 SW 역량테스트] 벌꿀채취  (0) 2019.08.05
[SWEA] 1952. [모의 SW 역량테스트] 수영장  (0) 2019.08.05
[SWEA] 4013. [모의 SW 역량테스트] 특이한 자석  (0) 2019.07.11

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

 

3190번: 뱀

문제  'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다. 뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따

www.acmicpc.net

이 문제에서 어려운 점은 뱀이 자기 몸에 부딪혀서 게임이 끝날때를 처리해주는 부분인 것 같다.

이 부분은 몸길이와 칸에 머리가 있었던 시간을 저장한 배열을 이용하면 쉽게 구할 수 있다.

 

(현재 시간 - 몸길이)가 이동할 칸에 이전에 머리가 있었던 시간보다 작으면 몸에 부딪힌 것 이다

 

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
#include <iostream>
#include <vector>
using namespace std;
 
int dx[] = { 0,1,0,-1 };
int dy[] = { 1,0,-1,0 };
 
 
int n, k;
 
//사과의 좌표를 저장
bool apple[100][100];
 
//머리가 위치한 시간을 저장
int headtime[100][100];
 
 
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie();
 
    cin >> n >> k;
 
    //사과정보 저장
    int ax, ay;
    for (int i = 0; i < k; i++) {
        cin >> ax >> ay;
        apple[ax - 1][ay - 1] = true;
    }
 
    int l;
    cin >> l;
    int t;
    char c;
 
    //방향 회전 정보를 저장
    vector<pair<int, char>> vt;
    for (int i = 0; i < l; i++) {
        cin >> t;
        cin >> c;
        vt.push_back(make_pair(t,c));
    }
 
    int time = 0;
 
    //방향 회전정보를 이용하기 위한 인덱스
    int index = 0;
 
    //초기 방향
    int dir = 0;
 
    //초기 길이
    int len = 1;
 
    //초기 위치는 좌측 맨위쪽
    int x = 0;
    int y = 0;
    while (true) {
        //먼저 시간증가, 길이 증가, 머리 앞칸으로 이동
        time++;
        len += 1;
        int nx = x + dx[dir];
        int ny = y + dy[dir];
        
        
        //벽에 부딪힘
        if (nx < 0 || ny < 0 || nx >= n || ny >= n) break;
 
        //몸에 부딪힘 ((현재 시간 - 몸길이)가 이동할 칸에 머리가 있었던 시간보다 작으면 몸에 부딪힌 것 이다)
        if (headtime[nx][ny] != 0 && ((time - len) < headtime[nx][ny])) break;
 
        //이동한 칸에 현재 시간을 저장
        headtime[nx][ny] = time;
 
        //사과가 있는지 검사
        if (apple[nx][ny]) {
            apple[nx][ny] = false;
        }
        else {
            len -= 1;
        }
 
 
        //l번만큼 방향이동을 한다.
        if (index < l) {
            //현재시간이 방향을 회전해야하는 시간이다
            if (time == vt[index].first) {
                if (vt[index].second == 'D') {
                    dir = (dir + 1) % 4;
                }
                else if (vt[index].second == 'L') {
                    dir = (dir + 3) % 4;
                }
 
                //방향 전환했으면 index증가 (다음 방향 정보를 이용하기 위해)
                index++;
            }
        }
        
        //현재 좌표를 머리가 이동한 칸의 좌표로 변경
        x = nx;
        y = ny;
    }
 
 
 
    cout << time << '\n';
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
  
저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 2234. 성곽  (0) 2019.08.13
[BOJ] 11559. Puyo Puyo  (0) 2019.08.08
[BOJ] 15683. 감시  (0) 2019.08.05
[BOJ] 14500. 테트로미노  (0) 2019.08.04
[BOJ] 14499. 주사위 굴리기  (0) 2019.08.04

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

 

15683번: 감시

스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감시할 수 있는 방법은 다음과 같다. 1번 CCTV는 한 쪽 방향만 감시할 수 있다. 2번과 3번은 두 방향을 감시할 수 있는데, 2번은 감시하는 방향이 서로 반대방향이어야 하고, 3번은 직각 방향이어야 한다. 4번은 세 방향, 5번은 네 방향을 감시할

www.acmicpc.net

CCTV구조체를 만들어서 CCTV의 좌표, 종류, 방향을 저장하게 했다.

방향은 나중에 모든 경우를 구해줄 때 저장한다.

모든 CCTV에 대해 방향을 정해줬으면 각 CCTV들의 감시 영역을 새로운 배열에 체크해주고

사각지대의 영역을 구해준다.

 

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
#include <iostream>
#include <vector>
using namespace std;
 
int n, m;
int ans;
int map[8][8];
int dx[] = { 0,-1,0,1 };
int dy[] = { -1,0,1,0 };
 
struct CCTV {
    //감시카메라의 좌표
    int x;
    int y;
 
    //감시카메라 종류 번호
    int num;
 
    //감시할 방향 (나중에 정해준다)
    int dir;
    CCTV(int x, int y, int num) : x(x), y(y), num(num){}
};
 
vector<CCTV> vt;
 
 
//감시영역을 체크
void start(int x, int y, int dir, int newmap[8][8]) {
    while (true) {
        //dir 방향으로 계속 감시 영역을 표시한다.
        x += dx[dir];
        y += dy[dir];
 
        //범위 체크
        if (x < 0 || y < 0 || x >= n || y >= m) break;
        //벽이면 넘어갈 수 없다.
        if (map[x][y] == 6) break;
 
        //감시영역에 적당히 그냥 7넣어줬다.
        newmap[x][y] = 7;
    }
}
 
 
//모든 감시카메라들을 지정된 방향에 따라 감시영역을 표시한다.
int solve() {
    int newmap[8][8];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            newmap[i][j] = map[i][j];
        }
    }
 
    int vsize = vt.size();
    int x, y, num,dir;
    for (int i = 0; i < vsize; i++) {
        x = vt[i].x;
        y = vt[i].y;
        num = vt[i].num;
        dir = vt[i].dir;
 
        //종류에 따라서 감시영역을 표시한다.
        if (num == 1) {
            //한방향 감시
            start(x, y, dir, newmap);
        }
        else if (num == 2) {
            //반대방향이 두방향 감시
            start(x, y, dir, newmap);
            start(x, y, (dir+2)%4, newmap);
        }
        else if (num == 3) {
            //직각모양 두방향 감시
            start(x, y, dir, newmap);
            start(x, y, (dir+1)%4, newmap);
        }
        else if (num == 4) {
            //세방향 감시
            start(x, y, dir, newmap);
            start(x, y, (dir + 1) % 4, newmap);
            start(x, y, (dir + 2) % 4, newmap);
        }
        else if (num == 5) {
            //네 방향 모두 감시
            start(x, y, dir, newmap);
            start(x, y, (dir + 1) % 4, newmap);
            start(x, y, (dir + 2) % 4, newmap);
            start(x, y, (dir + 3) % 4, newmap);
        }
    }
 
 
    //처음에 사각지대였는데 감시영역을 표시한 이후에도 사각지대이면 cnt증가
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (map[i][j] == 0 && newmap[i][j] == 0) cnt++;
        }
    }
 
 
    //사각지대 수를 리턴
    return cnt;
}
 
 
//모든 감시카메라에 대해서 방향을 정해준다.
void select(int index) {
    if (index == vt.size()) {
        int tmp = solve();
 
        if (ans > tmp) ans = tmp;
        return;
    }
 
    for (int i = 0; i <= 3; i++) {
        vt[index].dir = i;
        select(index + 1);
    }
    
 
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie();
 
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> map[i][j];
 
            //감시카메라이면 벡터에 넣는다.
            if (map[i][j] >= 1 && map[i][j] <= 5) {
                vt.push_back(CCTV( i,j,map[i][j] ));
            }
        }
    }
 
 
    //정답이 될 수 있는 값보다 큰 값을 미리 저장
    ans = 65;
    select(0);
 
    cout << ans << '\n';
 
    return 0;
}
Colored by Color Scripter
  
저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 11559. Puyo Puyo  (0) 2019.08.08
[BOJ] 3190. 뱀  (0) 2019.08.06
[BOJ] 14500. 테트로미노  (0) 2019.08.04
[BOJ] 14499. 주사위 굴리기  (0) 2019.08.04
[BOJ] 14503. 로봇 청소기  (0) 2019.08.04

+ Recent posts

티스토리툴바