B2261

개요

백준 문제 2261번을 풀면서 어려웠던 점과 코드를 정리한다.
소요 시간 : 180분
https://www.acmicpc.net/problem/2261

문제

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
const int MAX = 100000;
const int INF = 987654321;
int N;
vector <pair<int,int>> v;


int getCalDistance(int aIdx,int bIdx)
{
	int ax = v.at(aIdx).first;
	int ay = v.at(aIdx).second;
	int bx = v.at(bIdx).first;
	int by = v.at(bIdx).second;
	return pow(bx - ax,2) + pow(by-ay,2);
}

int getMinDistanceInRange(int start,int end)
{
	int result = INF;
	for(int i=start;i<=end;i++)
	{
		for(int j=i+1;j<=end;j++)
		{
			if(i!=j)
			{
				result = min(result,getCalDistance(i,j));
			}
		}
	}
	return result;
}

int dist(pair<int, int> p1, pair<int, int> p2) {
	return pow(p1.first - p2.first, 2) + pow(p1.second - p2.second, 2);
}


int getIdxFromDLeft(int d,int mid)
{
	int midX = v.at(mid).first -d;
	for(int i=0;i<v.size();i++)
	{
		if(v.at(i).first > midX)
		{
			return i;
		}
	}
	return -1;

}

int getIdxFromDRight(int d,int mid)
{
	int midX = v.at(mid).first +d;
	for(int i=v.size()-1;i>=0;i--)
	{
		if(v.at(i).first < midX)
		{
			return i;
		}
	}
	return -1;
}


int binCal(int start,int end)
{
	int result = INF;
	if(end - start + 1 <= 3)
	{
		for (int i=start; i<end; i++)
		{
	    	for (int j=i+1; j<=end; j++)
	    	{
	    		result = min(result,dist(v[i], v[j]));
	      	}
	    }
	}
	else
	{
		int mid= (start + end)/2;
		result = min(binCal(start,mid-1),binCal(mid+1,end));
		vector<pair<int, int>> tmp;
   		tmp.push_back({v[mid].second, v[mid].first});

   		for (int i=mid-1; i>=start; i--) {
	    	if (dist({v[mid].first, 0}, {v[i].first, 0})  >= result)
	    	{
	    		break;
	    	}
	    	tmp.push_back({v[i].second, v[i].first});// y축 순으로 정렬
    	}

    	for (int i=mid+1; i<=end; i++) {
	    	if (dist({v[mid].first, 0}, {v[i].first, 0})  >= result)
	    	{
	    		break;
	    	}
	    	tmp.push_back({v[i].second, v[i].first});// y축 순으로 정렬
    	}
    	sort(tmp.begin(), tmp.end());// y축 정렬

    	for (int i=0; i<tmp.size()-1; i++) {
      		for (int j=i+1; j<tmp.size(); j++) {
       			if (pow(tmp[i].first - tmp[j].first, 2) >= result)
       			{
       				break;
       			}
        		result = min(result, dist(tmp[i], tmp[j]));
        	}
    	}
	}
	return result;
}




void solve()
{
	cin >> N;
	int x,y;
	for(int i=0;i<N;i++)
	{
		cin >> x >> y;
		v.push_back(pair<int,int>(x,y));
	}
	sort(v.begin(),v.end());
	cout << binCal(0,N-1);
}

int main()
{
	solve();
}

풀이

학부 3학년 알고리즘 시간 배운 문제로 분할정복을 이용해서 풀어야 하는 흐름은 다음과 같다.

1. 전체 점에 대한 계산은 시간 문제가 크다.
2. 분할 정복을 이용해서 계산할 점의 범위를 줄인 뒤 계산하여 합쳐야한다.
3. 하지만 이 때 분할한 중심(이분 분할을 이용할 것이므로 중간값)을 기준으로 왼쪽과 오른쪽이 나뉘는데, 이 때 이 둘 사이의 거리가 큰 경우가 있을 수 있다.

배울 점, 메모

이분 분할을 기준으로 푸는데 접근한 것은 풀이 방법을 알고 있어 쉽게 접근할 수 있었음.
하지만 중간값에 대한 처리를 할 때 x축에 대해서 처리 한 것에 더해서 y축에 대해서도 처리해야 했는데 이 부분을 알 지 못했음.
또한 중간값에 대한 점들은 새로운 tmp라는 벡터로 관리를 하는데 기존 벡터에 더할려고 했어서 복잡해진 경향이 있음.