Bitonic > 문제은행

본문 바로가기


알고리즘 다이나믹2

1139 : Bitonic

제한시간: 1000 ms    메모리제한: 64 MB
해결횟수: 73 회    시도횟수: 118 회   



2차원 평면상에 n 개의 점이 주어져 있을 때, 어느 한 점부터 시작하여 모든 점을 한 번만 방문한 다음, 다시 그 점으로 돌아오는 가장 짧은 사이클(closed cycle)을 찾는 문제(이를 판매원 여행 문제(Travel Salesman Problem)이라 한다.)는 잘 알려진 NP-hard 문제로서 다항 시간(Polynomial time)내에 이 문제를 해결하는 알고리즘은 아직 존재 하지 않는다. 그러나, 이 문제를 다음과 같이 제한을 가하여 단순화하면 다항시간에 해결될 수 있음이 알려져 있다.

 

즉, 가장 왼쪽점부터 시작하여 x-좌표값이 증가하는 순서로 점을 방문하여 가장 오른쪽 점까지 도달한 다음, 다시 그 점부터 가장 왼쪽 점까지 x-좌표값이 감소하는 정렬의 순서대로 방문하는 가장 짧은 사이클을 찾는 것이다. 이러한 사이클을 Bitonic Cycle 이라고 부른다.

 

 

e3050b66a1b29a01767400d7560a4131_1449736e3050b66a1b29a01767400d7560a4131_1449737
 

 

위 두 그림 중 왼쪽 그림은 일반적인 TSP의 최적해이며, 오른쪽의 그림은 Bitonic Cycle 이다. TSP cycle 는 bitonic cycle 보다 전체길이가 더 짧거나 같다.

 

n 개의 점이 임의의 순서로 주어졌을 때 (단, 같은 x-좌표를 갖는 점들이 없다고 가정한다),이의 bitonic cycle 을 다항시간에 구하는 프로그램을 작성하라.


첫 번째 줄에는 점의 개수 n(1≤n≤100)이 주어지고, 둘째 줄부터 n 개의 줄에는 각 점의 좌표가 x,y 의 순서로 들어온다. 좌표는 -10,000 부터 10,000 까지이다.



bitonic cycle 의 길이를 소수점 둘째 자리까지 반올림하여 출력한다.


[Copy]
7
13 8
3 2
12 3
2 9
15 4
10 7
4 6
[Copy]
36.61




KOI4u 2012모의고사

HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.