보석( BOJ 2492 )

문제 : https://www.acmicpc.net/problem/2492

2492번: 보석

 

문제 파악하기

가장 많은 금광석을 포함하고 있는 K*K 크기의 정사각형 위치를 구하는 문제입니다. 지도의 크기인 N과 M의 범위는 크지만 묻혀있는 금광석의 개수는 최대 100개이기 때문에 탐색할 범위만 잘 설정하면 충분히 완전탐색으로도 해결할 수 있습니다. 그럼 탐색할 범위는 어떻게 구할 수 있을까요? 탐색할 범위를 구하기 앞서, 탐색할 영역이 정사각형이라는 점에 주목해야 합니다. 영역이 정사각형이기 때문에 우리는 왼쪽 하단의 좌표를 기준으로 탐색을 진행하면 중복 없이 효율적으로 탐색할 수 있습니다. 그럼 기준이 되는 왼쪽 하단의 좌표는 어떤 기준으로 뽑아야 할까요? 

 

문제 해결하기

왼쪽 하단의 좌표값은 지금까지 나온 모든 x좌표와 y좌표를 참고하면 됩니다. 단순히 점의 위치만 확인하면 누락되는 영역이 많습니다. 예를 들어 K=4이며, 8개의 금광석이 다음과 같은 좌표에 묻혀있다고 생각해봅시다.

(2, 2) / (3, 4) / (4, 3) / (4, 5) / (5, 3) / (6, 4) / (7, 5) / (7, 6)

 

금광석을 가장 많이 캘 수 있는 영역은 (3, 3)을 기준으로 한 영역입니다. 하지만 (3, 3)은 점의 좌표가 아닙니다. 이처럼 단순히 점의 위치만 확인해서는 최적값을 찾을 수 없습니다. 대신, 우리는 지금까지 나온 모든 x와 y 좌표값을 사용할 수 있습니다. 여기에 지도가 충분히 크지 않은 특수 케이스를 감안하여 (N-K)와 (M-K)의 값을 각각 x좌표와 y좌표에 추가하면 모든 경우에 대해 탐색할 수 있으며, 이 중에서 금광석을 가장 많이 찾을 수 있는 영역을 찾으면 됩니다. x좌표와 y좌표를 정렬하여 중복된 값을 제거하면 좀 더 효율적인 탐색이 가능합니다. 자세한 소스코드는 다음과 같습니다.

 

소스코드

#include <stdio.h>
#include <utility>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int, int> PAIR;
 
int N, M, T, K;
int x, y;
vector< PAIR > inp;
 
int retX, retY, retCnt;
vector< int > xy[2];
 
bool between(int a, int val, int b) { return a<=val and val<=b; }
 
int main() {
    // 입력
    scanf("%d %d %d %d", &N, &M, &T, &K);
    for(int i=0;i<T;i++) {
        scanf("%d %d", &x, &y);
        inp.emplace_back(x, y);
        
        xy[0].emplace_back(x);
        xy[1].emplace_back(y);
    }
    
    // x와 y값 추출(중복 제거)
    xy[0].emplace_back(N-K);
    xy[1].emplace_back(M-K);
    for(int k=0;k<2;k++) {
        sort(xy[k].begin(), xy[k].end());
        xy[k].erase(unique(xy[k].begin(), xy[k].end()), xy[k].end());
    }
    
    // 완전 탐색
    for(int curX:xy[0]) {
        for(int curY:xy[1]) {
            if(curX+K>N or curY+K>M) continue;
            
            int tmpCnt=0;
            for(int k=0;k<T;k++) tmpCnt += (between(curX, inp[k].first, curX+K) & between(curY, inp[k].second, curY+K));
            
            if(retCnt < tmpCnt) {
                retCnt = tmpCnt;
                retX = curX;
                retY = curY;
            }
        }
    }
    
    // 출력
    printf("%d %d\n", retX, retY+K);
    printf("%d", retCnt);
    
}
/*
10 6 7 3
2 2
3 4
7 6
4 5
4 3
5 3
6 4
ans
3 5
5
 
3 5 3 3
1 1
2 1
2 2
ans
0 3
3
*/
 

후기

반복문을 사용한 완전 탐색 문제입니다. 스위핑의 개념도 살짝 볼 수 있으며, 좌표값 압축도 실습할 수 있어 기본적인 알고리즘을 학습하고 소개하는데 좋은 문제라고 생각합니다.