그리스-로마 건축
문제 해석
두 건물이 지어진 가능한 위치와 크기를 구하는 문제입니다.
두 건물의 모양은 정사각형이고, 서로 겹칠 수 있습니다.
설계(20)
처음에 문제 자체를 해석하기 어려웠습니다.
건물이 있었다는 흔적인 ‘x’를 전부 포함하지 않는 경우도 가능한 경우인지 아닌지 명확히 제시되지 않은 것 같습니다.
테스트케이스와 대조해보면서 문제를 이해하였습니다.
결론은 확인해야 할 사항이 아래와 같습니다.
- 건물의 흔적을 모두 포함한 정사각형인지?
- 두 건물이 서로 겹칠 수 있다.(완전히 겹치는 것 포함)
극단적인 예로, 두 건물이 완벽히 겹쳐지는 것도 가능하다는 것을 인지해야 합니다.
저는 백트래킹 기법을 이용하여 문제를 해결하였습니다.
우선, 특정 좌표에서 시작하는 k길이의 범위가 정사각형인지 확인하는 부분에서 매 탐색마다 일일히 반복문으로 다시확인하게되면 시간초과가 날 것으로 보였습니다.
이를 최적화하기 위해서 누적합 방법을 이용하였습니다.
모든 좌표를 돌면서 만들 수 있는 정사각형을 두번째 건물까지 선택합니다.
두번째 건물까지 선택 완료하면, 1번 조건을 만족하는 지 확인합니다.
서로 겹친 부분이 있는 경우 그 면적만큼 감소시켜줘야 전체 면적을 구할 수 있습니다.
두개의 조건을 모두 만족하는 경우, 출력을 바로 하고 flag변수를 이용하여 백트래킹 함수를 빠져나갑니다.
구현(60)
코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define MAXN 101
struct node{
int sx,sy,ex,ey;
};
vector<node> vt;
char map[MAXN][MAXN];
int psum[MAXN][MAXN];
int N,M;
int sum = 0;
bool flag;
int calc(int x1, int y1 ,int x2, int y2){
return psum[x2][y2] - psum[x1-1][y2] - psum[x2][y1-1] + psum[x1-1][y1-1];
}
int calc(node a){
return calc(a.sx,a.sy,a.ex,a.ey);
}
void backtrack(int cnt){
if (flag) return;
if (cnt==2){
int tmp_sum = calc(vt[0]) + calc(vt[1]);
int sx = max(vt[0].sx,vt[1].sx);
int sy = max(vt[0].sy,vt[1].sy);
int ex = min(vt[0].ex,vt[1].ex);
int ey = min(vt[0].ey,vt[1].ey);
if (sx<=ex && sy <=ey){
tmp_sum -= calc(sx,sy,ex,ey);
}
if (tmp_sum != sum) return;
flag =true;
for (int i = 0 ;i < 2; i++){
printf("%d %d %d\n",vt[i].sx,vt[i].sy,(vt[i].ex-vt[i].sx+1));
}
return;
}
for (int i = 1; i<=N; i++){
for (int j= 1;j <=M; j++){
if (map[i][j] =='x'){
int idx = 0;
while (i+idx<=N && j+idx<=M && map[i+idx][j]=='x' && map[i][j+idx] =='x' && calc(i,j,i+idx,j+idx)==(idx+1)*(idx+1)) idx++;
if (idx!=0) idx--;
while (idx>=0){
if (calc(i,j,i+idx,j+idx) == (idx+1)*(idx+1)){
vt.push_back({i,j,i+idx,j+idx});
backtrack(cnt+1);
vt.pop_back();
idx--;
}
else break;
}
}
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin >> N >> M;
for (int i =1 ; i<=N; i++){
for (int j=1;j<=M;j++){
char tmp;
cin >> tmp;
map[i][j] = tmp;
int cnt = 0;
if (map[i][j] == 'x'){
cnt++;
sum++;
}
psum[i][j] = psum[i-1][j] + psum[i][j-1]-psum[i-1][j-1]+cnt;
}
}
backtrack(0);
return 0;
}
디버깅
두개의 정사각형이 서로 겹치는 경우를 체크할 때, 가능한 모든 경우를 나누어서 따로 처리해주었습니다.
그럴 필요 없이 min,max함수로 겹치는 부분을 한번에 체크할 수 있습니다.
완전히 겹치는게 안되는 것으로 이해하고 구현했었습니다. 완전히 겹치는 것을 방지하기 위해서 4차원 visited배열을 이용했었습니다.
지문을 잘못 이해한 것으로, visited배열을 제거하였습니다.
제출결과
4 ms
마무리
구현이 생각보다 까다로운 문제였습니다.
겹치는 부분을 한번에 체크하는 방법을 이번 기회로 알게 되었습니다. 아주 유용하게 쓰일 것 같습니다.