https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AW9j-qfacIEDFAUY&categoryId=AW9j-qfacIEDFAUY&categoryType=CODE

 

SW Expert Academy

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

swexpertacademy.com

이 문제는 구간 누적 합을 메모해 놓을 배열과 최솟값을 메모해 놓을 배열이 각각 필요하다.

 

다음과 같은 로직으로 풀어봤다.

 

  1. 입력받는다.
  2. 누적합을 dp로 만들어 놓는다.
    dp[x][y] = (0, 0)이 왼쪽 시작점 (x, y)과 오른쪽 끝점인 사각형의 누적합
  3. 초콜릿 자르는 모든 경우를 분할정복으로 구해준다.
    1. 가로로 자르는 경우(for문으로 가로 선택하는 모든 경우 구한다)
    2. 세로로 자르는 경우(for문으로 세로 선택하는 모든 경우 구한다)

위의 3번의 모든 경우 중 건포도의 수가 최소인 경우를 구해준다.
하지만 이때 진짜 다 구하면 시간 초과 발생하므로 미리 구해놓은 거는 메모해놨다가 써야 한다.

 

dp[x][y][ex][ey] = 초콜릿의 왼쪽 시작점이 (x, y) 오른쪽 끝점이 (ex, ey) 일 때 초콜릿을 자르는 경우 지불해야 하는 건포도의 최솟값

 

초콜릿의 크기가 클수록 다시 사용되는 부분이 계속 존재하므로 매번 다시 구할 필요가 없다. 그림으로 설명하면

아래 그림처럼 어떻게 잘라도 노란 사각형 부분을 잘랐을 때의 건포도의 최솟값은 동일하기 때문이다.

 

 

누적합을 구하는 방법은 백준의 2167번 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
#include <iostream>
#include <cstring>
#define MAX 1000000000
using namespace std;
 
int dp[51][51][51][51];
int choco[51][51];
int sum[51][51];
 
int solve(int x, int y, int ex, int ey) {
    //초코릿 조각이 한개면 0리턴
    if (x == ex && y == ey) return 0;
    //이미 최솟값을 구해놨으면 최솟값 바로 리턴
    if (dp[x][y][ex][ey] != -1) {
        return dp[x][y][ex][ey];
    }
 
    //(x, y)부터 (ex, ey)까지의 건포도의 합
    int cnt = sum[ex][ey] - sum[x - 1][ey] - sum[ex][y - 1] + sum[x - 1][y - 1];
 
 
    int rt = MAX;
 
    //가로로 자르는 경우
    for (int i = x; i < ex; i++) {
        int tmp = solve(x, y, i, ey) + solve(i + 1, y, ex, ey);
        if (rt > tmp + cnt) rt = tmp + cnt;
    }
 
    //세로로 자르는 경우
    for (int i = y; i < ey; i++) {
        int tmp = solve(x, y, ex, i) + solve(x, i + 1, ex, ey);
        if (rt > tmp + cnt) rt = tmp + cnt;
    }
 
 
    //dp메모하고 리턴
    return dp[x][y][ex][ey] = rt;
 
}
 
 
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
 
    int T;
    cin >> T;
 
    int n, m;
    for (int tc = 1; tc <= T; tc++) {
        //최솟값 dp배열 -1로 초기화
        memset(dp, -1, sizeof(dp));
        
        cin >> n >> m;
 
 
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                cin >> choco[i][j];
            }
        }
 
        //누적합
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + choco[i][j];
            }
        }
 
        int ans = solve(1, 1, n, m);
        cout << '#' << tc << ' ' << ans << '\n';
    }
 
 
    return 0;
}
Colored by Color Scripter
  

 

저작자표시

'SWEA > D4' 카테고리의 다른 글

[SWEA] 1486. 장훈이의 높은 선반  (0) 2019.06.27
[SWEA] 1226. [S/W 문제해결 기본] 7일차 - 미로1  (0) 2019.06.27
[SWEA] 7829. 보물왕 태혁  (0) 2019.06.27

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

 

SW Expert Academy

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

www.swexpertacademy.com

이 문제에서 어려운 부분은두 개 이상의 군집이 하나의 셀에 모이는 경우인 것 같다.

어떻게 처리를 해줘야하나 한참 고민을 했었고, 처음엔 틀렸었다...ㅎ

 

이 부분을 처리해주기 위해서 먼저 군집들의 정보를 저장하기 위해 구조체를 만들어줬다.

군집 정보에는 x, y 좌표, 미생물 수(cnt), 방향(dit), 그리고 추가적으로 미생물 수 합을 저장하는 변수 sum을 만들었다.

그리고 배열을 만들어서 배열의 x, y좌표에는 해당 위치에 있는 군집의 번호를 기록해줬다.

매시간마다 위치는 바뀌기 때문에 배열의 값도 바뀌어야 하는데 그냥 헷갈지않게 배열 전체를 -1로 초기화해버렸다.

 

이동할 위치의 값이 -1(초기값)인 경우에는 아무 군집도 존재하지 않으므로 바로 그 위치로 이동한다.

그렇지 않은 경우에는, 기록되어 있는 인덱스를 이용해서 해당 위치에 있는 군집의 미생물 수와 현재 군집의 미생물 수를 비교해준다.

 

현재 미생물 수(cnt)가 더 큰 경우에는 배열의 값을 현재 군집의 번호로 바꿔주고 이전 군집의 미생물 수의 합(sum의 값)을 현재 미생물 수의 합에 더해준다. 그리고 이전 군집의 cnt와 sum은 0으로 만들어줌으로써 없애준다. 반대의 경우에도 비슷한 방식으로 처리해준다.

 

sum 변수를 추가적으로 써주는 이유는 3개이상의 군집이 하나의 셀에 모일 수 있기 때문이다.

위와 같은 상황에서 또 다른 군집이 같은 위치에 왔을 때, 이미 있는 군집의 cnt와 비교를 해줘야 하기 때문이다

즉, 합쳐진 값인 sum과 비교를 하면 안된다. 그리고 다시 새로 온 군집의 cnt가 더 큰 경우에는 이전 군집의 sum(앞에서 합쳐진 두 개의 군집의 미생물수)를 현재 군집의 sum에 더해주고, 이전 군집의 cnt와 sum은 다시 0으로 만들어준다.

 

 

이런 식으로 현재시간에 군집들의 이동이 모두 끝났다면

미생물 수(cnt)를 합쳐진 값(sum)으로 바꿔주면 된다.

그리고 이제 사라진 애들은 이동할 필요가 없기 때문에 cnt가 0인 애들은 continue 해준다

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>
#include <cstring>
using namespace std;
 
int ans;
int n, m, k;
 
int dx[] = { 0,-1,1,0,0 };
int dy[] = { 0,0,0,-1,1 };
int map[100][100];
 
struct Group {
    int x;
    int y;
    int cnt;
    int dir;
    int sum;
    Group(int x, int y, int cnt, int dir, int sum) : x(x), y(y), cnt(cnt), dir(dir), sum(sum) {}
};
 
vector<Group> vt;
 
 
void solve() {
    
    int time = 0;
 
    //m시간 동안 진행
    while (time++ < m) {
        memset(map, -1, sizeof(map));
 
        //모든 군집 이동
        int x, y, cnt, dir;
        for (int i = 0; i < k; i++) {
            //사라진 군집은 이동하지 않는다.
            if (vt[i].cnt == 0) continue;
 
            //일단 값들 변수에 꺼내놓는다.
            x = vt[i].x;
            y = vt[i].y;
            cnt = vt[i].cnt;
            dir = vt[i].dir;
 
            //이동
            x += dx[dir];
            y += dy[dir];
 
 
            //이동한 좌표 새로 저장
            vt[i].x = x;
            vt[i].y = y;
 
 
            //약품이 칠해진 구역이면 미생물 수 반으로 감소 후 방향 반대로 전환
            if (x == 0 || y == 0 || x == n - 1 || y == n - 1) {
                vt[i].cnt /= 2;
                vt[i].sum /= 2;
                if (dir == 1 || dir == 3) {
                    vt[i].dir += 1;
                }
                else {
                    vt[i].dir -= 1;
                }
            }
            else {
                //약품이 칠해지지 않은 구역인 경우
                //이동한 곳에 아무도 없으면 현재 군집 번호를 저장
                if (map[x][y] == -1) {
                    map[x][y] = i;
                }
                else {
                    //이동한 곳에 이미 다른 군집이 있다
 
                    //이미 있는 군집의 미생물 수가 더 큰 경우
                    if (cnt < vt[map[x][y]].cnt) {
                        //현재 군집의 미생물 수의 합을 합쳐주고
                        vt[map[x][y]].sum += vt[i].sum;
 
                        //현재 군집은 없애준다.
                        vt[i].cnt = 0;
                        vt[i].sum = 0;
                    }
                    else {
                        //현재 군집의 미생물 수가 더 큰 경우
 
                        //이전 군집의 미생물 수 합을 현재 군집의 합에 더해주고
                        vt[i].sum += vt[map[x][y]].sum;
 
                        //이전 군집은 없애준다.
                        vt[map[x][y]].cnt = 0;
                        vt[map[x][y]].sum = 0;
 
                        //현재 군집의 번호를 새로 저장해준다.
                        map[x][y] = i;
                    }
 
                }
 
            }
 
 
 
        }
 
 
        //모든 군집의 이동이 끝났으면 합쳐진 미생물의 합을 군집의 미생물 개수로 바꿔준다.
        for (int i = 0; i < k; i++) {
            vt[i].cnt = vt[i].sum;
        }
 
    }
 
    //남은 미생물의 수를 세준다.
    for (int i = 0; i < k; i++) {
        ans += vt[i].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;
        vt.clear();
 
        cin >> n >> m >> k;
 
        int x, y, cnt, dir;
        for (int i = 0; i < k; i++) {
            cin >> x >> y >> cnt >> dir;
            vt.push_back(Group(x, y, cnt, dir, cnt));
        }
 
        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] 5644. [모의 SW 역량테스트] 무선 충전  (0) 2019.08.07
[SWEA] 2112. [모의 SW 역량테스트] 보호 필름  (0) 2019.08.07
[SWEA] 5656. [모의 SW 역량테스트] 벽돌 깨기  (0) 2019.08.06

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

 

SW Expert Academy

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

www.swexpertacademy.com

빈칸인 모든 칸으로부터  상하좌우 네 방향으로 모두 출발해보고 점수를 구하면된다. 그렇게 나온 점수 중 최댓값이 정답이다.

 

게임을 시작했으면 이동한 칸에 따라 처리해주면 된다.

 

1. 범위를 넘어간 경우(벽에 부딪힌 경우)에는 점수를 얻고 방향 전환 후에 바로 다음 칸으로 이동한다.

2. 출발 위치로 돌아오면 게임 종료

3. 블랙홀(-1)이면 게임 종료

4. 빈칸인 경우 계속 방향대로 이동

5. 블록인 경우(1~5)에는 각 블록의 방향에 맞게 방향을 전환해주고 점수를 얻는다.

6. 웜홀인 경우 같은 번호의 반대편 웜홀로 이동

 

 

웜홀의 경우에는 다음과 같이 x,y좌표를 가지는 벡터를 배열에 저장해서 구현하였다.

예를 들어 5번 웜홀의 좌표는 wormhole[0][0]과 wormhole[0][1]에 각각 들어있고, 6번 웜홀은 wormhole[1][0]과 wormhole[1][1]에 각각 들어있다. 게임판 배열에 들어있는 값에서 5를 빼준 값을 wormhole 배열의 인덱스로 사용하면 된다. (ex. 6번 웜홀의 인덱스는 1번)

 

wormhole 0(5번)

1(6번)

 2(7번) 3(8번) 4(9번) 5(10번)
0 (x,y) (x,y) (x,y) (x,y) (x,y) (x,y)
1 (x,y) (x,y) (x,y) (x,y) (x,y) (x,y)

 

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
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
 
int n, ans;
int map[100][100];
int dx[] = { -1,0,1,0 };
int dy[] = { 0,1,0,-1 };
 
 
vector<pair<int, int>> wormhole[5];
 
void start(int x, int y, int dir) {
 
    int point = 0;
    int nx = x;
    int ny = y;
    while (true) {
 
        //이동
        nx += dx[dir];
        ny += dy[dir];
 
        //벽에 부딪힘
        if (nx < 0 || ny < 0 || nx >= n || ny >= n) {
            point++;
 
            //반대 방향으로 바꿔준다.
            if (dir == 0 || dir == 1) {
                dir += 2;
            }
            else {
                dir -= 2;
            }
 
            //다음이동으로 바로 넘어감
            continue;
        }
 
 
        //출발위치로 돌아오면 게임 종료
        if (x == nx && y == ny) {
            break;
        }
 
        //블랙홀에 빠지면 게임 종료
        if (map[nx][ny] == -1) {
            break;
        }
 
        
        //빈칸이면 계속이동
        if (map[nx][ny] == 0) continue;
 
 
        //블록인 경우
        if (map[nx][ny] == 1) {
            if (dir == 0 || dir == 1) {
                dir += 2;
            }
            else if (dir == 2) {
                dir = 1;
            }
            else {
                dir = 0;
            }
 
            point++;
        }
        else if (map[nx][ny] == 2) {
            if (dir == 1) {
                dir = 3;
            }
            else if (dir == 2) {
                dir = 0;
            }
            else if (dir == 3) {
                dir = 2;
            }
            else {
                dir = 1;
            }
 
            point++;
        }
        else if (map[nx][ny] == 3) {
            if (dir == 0) {
                dir = 3;
            }
            else if (dir == 1) {
                dir = 2;
            }
            else if (dir == 2) {
                dir = 0;
            }
            else {
                dir = 1;
            }
 
            point++;
        }
        else if (map[nx][ny] == 4) {
            if (dir == 0) {
                dir = 2;
            }
            else if (dir == 1) {
                dir = 0;
            }
            else if (dir == 2) {
                dir = 3;
            }
            else {
                dir = 1;
            }
 
            point++;
        }
        else if (map[nx][ny] == 5) {
            dir = (dir + 2) % 4;
            point++;
        } else if (map[nx][ny] >= 6 && map[nx][ny] <= 10) {
            //웜홀인 경우
            int num = map[nx][ny] - 6;
 
            //0번에 있는 좌표와 같으면 1번에 있는 좌표로 이동
            if (wormhole[num][0].first == nx && wormhole[num][0].second == ny) {
                nx = wormhole[num][1].first;
                ny = wormhole[num][1].second;
            }
            else { //1번에 있는 좌표와 같은 경우이므로 0번에 있는 좌표로 이동
                nx = wormhole[num][0].first;
                ny = wormhole[num][0].second;
            }
        }
    }
 
    //점수의 최대값을 저장
    if (ans < point) ans = point;
 
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int T;
    cin >> T;
    for (int tc = 1; tc <= T; tc++) {
        cin >> n;
 
        ans = 0;
        for (int i = 0; i < 5; i++) {
            wormhole[i].clear();
        }
 
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                cin >> map[i][j];
                
                //웜홀이면 벡터 배열에 저장
                if (map[i][j] >= 6 && map[i][j] <= 10) {
                    wormhole[map[i][j] - 6].push_back(make_pair(i, j));
                }
            }
        }
 
 
        //모든 빈칸에서 네방향으로 출발
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (map[i][j] != 0) continue;
 
                for (int k = 0; k < 4; k++) {
                    start(i, j, k);
                }
 
            }
        }
 
        cout << '#' << tc << ' ' << ans << '\n';
    }
 
 
    return 0;
}
Colored by Color Scripter
  
저작자표시

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

[SWEA] 2382. [모의 SW 역량테스트] 미생물 격리  (0) 2019.08.08
[SWEA] 1953. [모의 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=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

+ Recent posts

티스토리툴바