- 본 문제는 영어로 Closest pair of points problem라고 하며 한국어로는 최근점 점쌍 문제라고 부른다. 


- 본 문제에서 풀고자 하는 것은 2차원 좌표평면에 n개의 점이 주어졌을 때, 이 점들 중 가장 가까운 두 점을 구하는 프로그램을 작성하는 것이다. 


- 사실 처음에는 그냥 2중 for문을 사용해서 구현하면 되는 단순한 문제인줄 알았지만, 계속 시간초과가 발생하여 무엇인 문제인지 찾아봤고, 이 문제는 부루투 포싱을 통해 가장 가까운 두 점을 찾는 문제가 아니라 분할정복 알고리즘을 구현하여 두 점을 찾는 문제임을 알게 되었다..


- 알고리즘에 대한 설명은 [1]에 나와있고, 내가 문제에 대한 상세는 [2]에 나와있다.

- 번거로움을 줄이기 위해 위키피디아[1]에 정리되어 있는 알고리즘의 개요를 그림으로 포스팅한다.








Baek Joon Online Judge[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
#include < stdlib.h >
#include < algorithm >
 
using std::sort;
using std::pair;
 
#define Min(a,b)    (((a) < (b)) ? (a) : (b))
#define Inf 999999999
#define SIZE 100000
 
typedef pair <int, int>  Pairs;
 
int eDist(Pairs mF, Pairs mS){
    int x = (mS.first - mF.first);
    int y = (mS.second - mF.second);
    return (x*x) + (y*y);
}
 
 
int seperator(Pairs * mPDot, const int idx){
    Pairs * left;
    Pairs * right;
 
    int dist = Inf;
    int dist1 = Inf;
    int dist2 = Inf;
    int dist3 = Inf;
    int distMid = Inf;
         
    if(idx == 3){
        dist1 = eDist(mPDot[idx-3], mPDot[idx-2]);
        dist2 = eDist(mPDot[idx-3], mPDot[idx-1]);
        dist3 = eDist(mPDot[idx-2], mPDot[idx-1]);
 
        dist = Min(dist1, dist2);
        dist = Min(dist, dist3);
    }  
    else if(idx == 2){
        dist = eDist(mPDot[idx-2], mPDot[idx-1]);
    }
    else {
        left = &(mPDot[0]);
        right = &(mPDot[idx/2]);
 
        dist = Min(seperator(left, idx/2), seperator(right, idx/2));
     
        for(int i=(idx/2)-1; i > =0; i--){
            for(int j=0; j < idx/2; j++){
                if( dist > ((left[i].first - right[j].first) * (left[i].first - right[j].first)) ){
                    distMid = eDist(left[i], right[j]);
                    dist = Min(dist, distMid);
                }
                else break;
            }
        }
    }
    return dist;
}
 
int main(void){
    int N = 0;
    scanf("%d", &N);
 
    Pairs pDot[SIZE];
     
    int x, y;
    for(int n=0; n < N; n++){
        scanf("%d %d", &x, &y);
        pDot[n] = Pairs (x, y);
    }
    sort(&(pDot[0]), &(pDot[0+N]));
    printf("%d\n", seperator(pDot, N));
 
    return 0;
}

References:

[1] https://ko.wikipedia.org/wiki/최근접_점쌍_문제

[2] https://www.acmicpc.net/problem/2261


'Algorithms' 카테고리의 다른 글

[ACM-ICPC Baek Joon] Quadtree  (0) 2017.07.14
Posted by Hugh_K
l

본 문제는 쿼드트리라는 일종의 압축기법에 대한 문제이다. 쿼드트리의 규칙에 맞게 압축하여 결과물을 출력하는 코드를 작성하면 된다. 


문제는 "acmicpc.net"의 1992번 문제[1]이며 원문은 아래와 같다. 





쿼드트리라는 기법에 대한 자세한 설명은 위키피디아[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
constQueue = list()
 
def makeSqure(mData):
    oData = list()
    sNum = 0
         
    for n in range(1, 64):
        sNum = len(mData)/n
        if sNum == n: break
     
    j = 0
    oData.append(list())
    for i in range(len(mData)):
        if i%sNum == 0:
            oData.append(list())
            j = j+1
        oData[j].append(mData[i])
 
    del oData[0]
             
    return oData
 
 
def all_01(sData, mN):
 
    cList = list()
    for i in range(mN):
        for j in range(mN):
            cList.append(sData[j][i])
 
    if len(list(set(cList))) != 1:
        sepData0 = list()
        sepData1 = list()
        sepData2 = list()
        sepData3 = list()
 
        for i in range(mN):
            for j in range(mN):
                if i < mN/2 and j < mN/2:
                    sepData0.append(sData[i][j])
                elif i < mN/2 and j >= mN/2:
                    sepData1.append(sData[i][j])
                elif i >= mN/2 and j < mN/2:
                    sepData2.append(sData[i][j])
                elif i >= mN/2 and j >= mN/2:
                    sepData3.append(sData[i][j])
 
 
        constQueue.append("(")
        all_01(makeSqure(sepData0), mN/2)
        all_01(makeSqure(sepData1), mN/2)
        all_01(makeSqure(sepData2), mN/2)
        all_01(makeSqure(sepData3), mN/2)
        constQueue.append(")")
 
    else:
        constQueue.append(str(cList[0]))
     
if __name__=="__main__":
    N = int(input())
    if N == 0:
        exit()
 
    scene = list()
    for n in range(N):
        ln = str(raw_input())
        scene.append([ln[n] for n in range(len(ln))])
 
    all_01(scene, N)
 
    print "".join(constQueue)


P.S. 큐나 스텍 같은 자료구조를 이용해 출력했다면 더 고급스러워 보였겠지만, 귀찮음으로 인해 그냥 전역변수 리스트를 하나 사용했다.....





References:

[1] https://www.acmicpc.net/problem/1992

[2] https://en.wikipedia.org/wiki/Quadtree

'Algorithms' 카테고리의 다른 글

[ACM-ICPC Baek Joon] Closest pair of points problem  (0) 2017.07.14
Posted by Hugh_K
l

[Network] Network node size estimation

2017. 7. 4. 15:27 by Hugh_K

보호되어 있는 글입니다.
내용을 보시려면 비밀번호를 입력하세요.