BOJ 17941번
풀이 알고리즘 : 세그먼트 트리, 슬라이딩 윈도우
2020년도 UCPC를 연습할 겸 풀어본 대회(HCPC)에 있는 문제입니다.
문제를 간단히 다시 설명하면, N x M 크기의 목장에 양들이 있고, 양들은 크기가 정해져 있습니다.
그 목장에 CCTV를 설치하는데 CCTV는 아래로 r, 오른쪽으로 c만큼 크기의 직사각형을 촬영합니다. 특이하게, 이 CCTV는 촬영한 범위 내의 가장 큰 양의 크기를 알려줍니다.
그리고 방향을 나타내는 정수 D가 주어지는데, 이는 모든 양들이 상/하/좌/우 중 입력된 한 방향으로 하루에 한칸씩 이동합니다.
그래서 문제에서는 K일 동안 촬영했을 때, 각 촬영마다 촬영한 가장 큰 양의 크기를 모두 XOR한 값을 출력하는게 목표입니다.
이때 주의해야 할 점은, 문제에서 CCTV의 좌표가 X, Y로 입력이 된다고 하는데, 실제로 X는 y좌표로 입력이 되고, Y는 x좌표로 입력이 되므로 혼동하지 않아야 합니다.
문제에서 양이 상/하/좌/우 한 방향을 정하여 하루마다 방향대로 이동한다고 하였습니다. 이를 문제를 풀기위해, 고정되어 있는 CCTV를 양의 반대방향으로 이동시킨다고 생각을 했습니다.
즉, 양이 상/하/좌/우로 이동한다면, 상대적으로 CCTV가 하/상/우/좌 순서로 한칸씩 이동하는 것과 같습니다.
문제에서 촬영범위 안에 빈 공간이 생기는 경우는 주어지지 않는다고 하므로, 이동했을 때 인덱스를 초과하는 경우는 발생하지 않습니다.
만약 양이 오른쪽으로 이동한다고 가정해봅시다.
상대적으로 CCTV가 왼쪽으로 이동하는 상황과 동일합니다. 그럼 어떤일이 일어날까요?
그림과 같이 y = Y부터 높이 R만큼의 목장을, R x C 크기의 CCTV가 양의 이동방향의 반대인 왼쪽으로 이동하면서 최댓값을 찾는것과 동일합니다.
그러면 각각의 최댓값은 어떻게 구할까요? 쿼리의 개수가 많기때문에 최대값을 구하는 과정은 빨라야만 합니다.
그래서 이를 위해 세그먼트 트리를 이용해 최댓값을 빠르게 구했습니다.
세그먼트 트리에서 저장하는 값을 구간에서의 최댓값으로 저장하게 되면, 원하는 구간의 최댓값을 굉장히 빠르게 구할 수 있습니다.
일반적으로 재귀를 통해 세그먼트 트리를 구현하게 되는데, 이번 문제의 경우 쿼리의 수가 많아서 재귀를 통해 구현하게 되면, 재귀함수를 호출하는 빈도가 많아 느려지게 됩니다. 그래서 비재귀로 세그먼트 트리를 구현하였습니다.
그러나 2차원 배열에서의 세그먼트 트리를 구현하는것은 쉽지 않습니다.
그래서 제가 사용한 방법은 2차원 배열을 각 행마다의 세그먼트 트리의 배열과, 각 열마다의 세그먼트 트리의 배열 두개로 나누었습니다.
각 가로줄을 확인하고, 각 줄마다의 최댓값 세그먼트 트리를 구성하여 저장합니다.
세그먼트 트리 배열을 모아놓은 배열을 lrSegTree로 구성하였고, lrSegTree[i]는 i번째 가로줄의 세그먼트 트리를 나타냅니다.
마찬가지로 같은방법으로 udSegTree가 구현되었고, udSegTree[i]는 i번째 세로줄의 세그먼트 트리를 나타냅니다.
이제 세그먼트 트리가 구성이 되었으므로 각 쿼리마다 처리를 해주어야 합니다.
1.먼저 입력받은 양의 이동방향이 상/하 인지 좌/우 인지 확인합니다.
2. 상하로 이동한다면 각 가로줄마다에서 입력받은 CCTV의 X범위만큼의 최댓값을 구합니다.
3. 좌우로 이동한다면 각 세로줄마다에서 입력받은 CCTV의 Y범위만큼의 최댓값을 구합니다.
여기까지 구하면 cur 배열에는 CCTV가 상/하 또는 좌/우로 움직였을 때, 각 가로줄/세로줄의 CCTV의 범위에서의 최댓값이 들어있습니다.
그래서 이를 슬라이딩 윈도우 기법을 통해 탐색을 하면서 하루마다의 최댓값을 구하여 XOR해주면 됩니다.
이번 문제 해결을 위해서 슬라이딩 윈도우를 공부했는데, CCTV의 범위처럼 정해져있는 구간이 일정한 크기만큼 이동하면, 이동했을 때 새로 들어온 입력값만 가지고 최댓값을 빠르게 갱실할 수 있습니다.
다음은 정답코드입니다. (코드가 깁니다. 주의)
#include <bits/stdc++.h>
// 2의 제곱수 판정
#define POW2(X) (X) == ((X)&(-(X)))
// int pair 간단히
#define pii pair<int, int>
#define mp(X, Y) make_pair(X, Y)
// 기본설정
typedef long long ll;
using namespace std;
int dirx[4] = {1, 0, -1, 0};
int diry[4] = {0, 1, 0, -1};
/*
세그먼트 트리를 초기화 하는 함수
arr : 배열, tree : 세그먼트 트리, arr_size : 배열의 길이
*/
void init(int arr[], int tree[], int arr_size) {
// 리프 노드를 초기화
for(int i = 1; i <= arr_size; i++) {
tree[arr_size + i - 1] = arr[i];
}
// 나머지 트리를 빌드
for(int i = arr_size - 1; 0 < i; i--) {
tree[i] = max(tree[2 * i], tree[2 * i + 1]);
}
return;
}
int seg_max(int tree[], int le, int ri, int arr_size) {
int ans = 0;
// 리프 노드로 le, ri 이동
le += arr_size - 1;
ri += arr_size - 1;
// le, ri의 값이 홀수
do {
if(le % 2 == 1) {
ans = max(ans, tree[le++]);
}
if(ri % 2 == 1) ans = max(ans, tree[--ri]);
le /= 2;
ri /= 2;
} while(le < ri);
return ans;
}
int main(void) {
cin.tie(NULL);
ios_base::sync_with_stdio(false);
// 세로 길이 n, 가로 길이 m, 쿼리의 개수 query
int n, m, query;
/*
목장 각각의 가로줄, 세로줄에서의 양의 길이
lr[세로길이 n][가로길이 m]
ud[가로길이 m][세로길이 n]
*/
int lr[500 + 1][500 + 1] = {0}, ud[500 + 1][500 + 1] = {0};
/*
목장 각각의 가로줄/세로줄에서 최댓값을 저장하는 세그먼트 트리
lrSegTree[세로 길이 n][트리의 길이]
udSegTree[가로 길이 m][트리의 길이]
*/
int lrSegTree[500 + 1][1024 + 1] = {0}, udSegTree[500 + 1][1024 + 1] = {0};
// 사이즈 입력
cin >> n >> m;
// 배열 입력 (목장의 크기)
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
int sheep_size; cin >> sheep_size;
lr[i][j] = ud[j][i] = sheep_size;
}
}
// 각 가로줄에 대한 최댓값 세그먼트 트리 생성 (n개)
for(int i = 1; i <= n; i++) {
init(lr[i], lrSegTree[i], m);
}
// 각 세로줄에 대한 최댓값 세그먼트 트리 생성 (m개)
for(int i = 1; i <= m; i++) {
init(ud[i], udSegTree[i], n);
}
// 쿼리의 개수 입력
cin >> query;
while(query--) {
// CCTV의 좌표 (y, x), CCTV의 범위 (r, c), 촬영 날짜 k, 이동방향 d, 출력값 ans
int y, x, r, c, k, d, ans = 0;
/*
각 가로줄/세로줄에서 범위 내 최대값을 저장한 배열
cur[i] : i번째 가로줄/세로줄에서 범위 내 최대값
*/
int cur[500 + 1] = {0};
/*
슬라이딩 윈도우에서 사용할 덱
deque <양의 크기, 해당 인덱스>
*/
deque<pii> dq;
// 입력
cin >> y >> x >> r >> c >> k >> d;
if(d < 3) {
/*
상하로 움직일 경우 i번째 세로줄에서 범위 내 가로줄에서의 최대값을 저장
각각의 가로줄에서의 범위 : [x, x + c)
*/
for(int i = 1; i <= n; i++) {
cur[i] = seg_max(lrSegTree[i], x, x + c, m);
}
} else {
/*
좌우로 움직일 경우 i번째 가로줄에서 범위 내 세로줄에서의 최대값을 저장
각각의 세로줄에서의 범위 : [y, y + r)
*/
for(int i = 1; i <= m; i++) {
cur[i] = seg_max(udSegTree[i], y, y + r, n);
}
}
// k회만큼 촬영
for(int i = 0; i < k; i++) {
if(i == 0) { // 첫번째 반복에서는 빈 덱을 채움
if(d == 1) {
int limit = y + r;
for( ; y < limit; y++) {
while(!dq.empty() && r <= abs(dq.front().second - y)) {
dq.pop_front();
}
while(!dq.empty() && dq.back().first <= cur[y]) {
dq.pop_back();
}
dq.push_back(mp(cur[y], y));
}
y--;
} else if(d == 2) {
int temp, limit = y + r;
for(temp = limit - 1; y <= temp; temp--) {
while(!dq.empty() && r <= abs(dq.front().second - temp)) {
dq.pop_front();
}
while(!dq.empty() && dq.back().first <= cur[temp]) {
dq.pop_back();
}
dq.push_back(mp(cur[temp], temp));
}
y = temp + 1;
} else if(d == 3) {
int limit = x + c;
for( ; x < limit; x++) {
while(!dq.empty() && c <= abs(dq.front().second - x)) {
dq.pop_front();
}
while(!dq.empty() && dq.back().first <= cur[x]) {
dq.pop_back();
}
dq.push_back(mp(cur[x], x));
}
x--;
} else if(d == 4) {
int temp, limit = x + c;
for(temp = limit - 1; x <= temp; temp--) {
while(!dq.empty() && c <= abs(dq.front().second - temp)) {
dq.pop_front();
}
while(!dq.empty() && dq.back().first <= cur[temp]) {
dq.pop_back();
}
dq.push_back(mp(cur[temp], temp));
}
x = temp + 1;
}
} else { // 나머지 시행에서는 새로 들어오는 입력값을 확인
if(d < 3) {
while(!dq.empty() && r <= abs(dq.front().second - y)) {
dq.pop_front();
}
while(!dq.empty() && dq.back().first <= cur[y]) {
dq.pop_back();
}
dq.push_back(mp(cur[y], y));
} else {
while(!dq.empty() && c <= abs(dq.front().second - x)) {
dq.pop_front();
}
while(!dq.empty() && dq.back().first <= cur[x]) {
dq.pop_back();
}
dq.push_back(mp(cur[x], x));
}
}
ans = ans ^ dq.front().first;
if(d == 1) y++;
else if(d == 2) y--;
else if(d == 3) x++;
else x--;
}
cout << ans << "\n";
}
return 0;
}'백준_BOJ > BOJ (플래티넘)' 카테고리의 다른 글
| [백준/알고리즘] 8986번 전봇대 (플래티넘 5) (1) | 2020.06.13 |
|---|
