[2교시]02. 대피소
2차원 평면의 KOI 마을에 N개의 집이 있다. 각 i번째 집의 위치는 (Xi
, Yi)이다.
i번째 집과 j번째 집 사이의 거리는 |Xi − Xj | + |Yi − Yj |이다. 즉, 두 집 사이의 거리는 X의 차이와 Y 의
차이의 합이다. 예를 들어, (1, 6)에 위치한 집과 (2, 4)에 위치한 집은 (2 − 1) + (6 − 4)인 3만큼 떨어져 있다.
KOI 마을은 재난 발생 시 주민들이 안전하게 대피할 수 있도록 K개의 집에 대피소를 설치할 계획이다. 모
든 주민의 안전을 고려하여, 집에서 가장 가까운 대피소로 이동할 때 가장 긴 거리가 최소가 되도록 대피소를
설치할 K개의 집을 선택하고, 그때 대피소와 가장 멀리 떨어진 집과의 거리를 구하려고 한다.
아래는 5개의 집이 각각 (1, 5), (3, 0), (3, 3), (6, 12), (8, 9)에 위치한 마을의 예이다.
이 마을에 2개의 대피소를 설치하려고 한다. 만약 (3, 0)과 (1, 5)에 위치한 집에 대피소를 설치한다면
설치하지 않은 나머지 세 집에서 가까운 대피소까지의 거리가 각각 3, 11, 12이고, 이 중 가장 먼 거리는 12
이다.
하지만 (3, 3)와 (6, 12)에 위치한 집에 대피소를 설치하면 가장 가까운 대피소와 가장 멀리 떨어져 있는
집은 (8, 9)에 위치한 집으로, (6, 12)와 5만큼 떨어져 있다. 대피소를 어떻게 설치해도 최대 거리가 5보다 작아지는 경우가 없으므로 5가 구하고자 하는 거리가 된다.
KOI 마을의 집들의 위치와 설치할 대피소의 개수가 주어질 때, 대피소를 설치하는 모든 방법 중 가장
가까운 대피소와 집 사이의 거리 중 가장 큰 값이 가장 작을 때의 거리를 구해라.
제약 조건
- • 주어지는 모든 수는 정수이다.
- • 1 ≤ K ≤ 3
- • K ≤ N ≤ 50
- • 0 ≤ Xi ≤ 100 000
- • 0 ≤ Yi ≤ 100 000
- • 같은 위치에 집이 여럿 존재하지 않는다. 즉, (X1, Y1), (X2, Y2), · · ·, (XN , YN )는 서로 다르다.
부분문제
- (5점) N = K + 1
- (7점) K = 1, 모든 i (1 ≤ i ≤ N)에 대해 Xi = i이고 Yi = 0이다.
- (10점) K = 1
- (18점) K = 2
- (35점) K = 3, 1 ≤ i ≤ N − 1에 대해 Xi < Xi+1이며, 모든 i (1 ≤ i ≤ N)에 대해 Yi = 0이다. 즉, X
는 오름차순으로 정렬되어 있다. - (25점) K = 3
입력 형식
첫 번째 줄에 N과 K가 공백을 사이에 두고 주어진다.
다음 N개의 줄에는 집의 위치가 주어지는데, 이 중 i (1 ≤ i ≤ N)번째 줄에는 Xi와 Yi가 공백을 사이에
두고 주어진다.
출력 형식
첫 번째 줄에 답을 출력한다.
========== 풀이 C ==========
대상이 50개정도면 모든 경우의 수를 다 점검 해봐도 될듯 합니다.
O(N4)
#include
#include
typedef struct _Point{
int x;
int y;
} Point;
Point points[50]; //집들의 위치는 최대 50개
Point shelters[3]; // 대피소 개수 최대 3개
int main(){
int N; // 집 개수
int K; // 대피소 개수
int t;
int mt=0; //현재 대피소에서 가장 먼 거리의 값
int mt1=0;
int mt2=0;
int mt3=0;
int correct=200000; //각 대피소에서 최대거리가 가장 잛은 거리의 값
scanf("%d%d",&N,&K);
for(int i=0;i scanf("%d%d",&points[i].x,&points[i].y);
}
if(K==1){ //대피소가 하나인 경우
for(int i=0;i mt = 0;
for(int j=0;j if(i==j) continue; // 같은 위치이므로 거리 측정에서 제외
t = abs(points[i].x - points[j].x) + abs(points[i].y - points[j].y);
if(t>mt) mt = t;
}
if(correct > mt ) correct = mt;
}
}else if(K==2){
for(int i=0;i for(int j=0;j if(i==j) continue; // 같은 집에 2개의 대피소를 설치 할 수 없다.
mt = 0;
for(int k=0;k if(k==i || k==j) continue; // 현재 집이 대피소 중 한곳이면 중단
//2개의 대피소중 짧은 거리가 최대인 값을 찾아야 한다.
mt1 = abs(points[i].x - points[k].x) + abs(points[i].y - points[k].y);
mt2 = abs(points[j].x - points[k].x) + abs(points[j].y - points[k].y);
//2개의 대피소 까지 거리중 최소 거리
mt1 = (mt1 > mt2) ? mt2: mt1;
if(mt1>mt) mt = mt1; // 짧은 거리중 최대
}
if(correct > mt ) correct = mt;
}
}
}
else if(K==3){
for(int i=0;i for(int j=0;j if(i==j) continue; // 대피소 중복 설치
for(int k=0;k if(i==k || j==k) continue; // 대피소 중복 설치
mt = 0;
for(int ii=0;ii if(ii==i || ii==j || ii==k) continue; //현재 집이 대피소 중 한곳이면 중단
mt1 = abs(points[i].x - points[ii].x) + abs(points[i].y - points[ii].y);
mt2 = abs(points[j].x - points[ii].x) + abs(points[j].y - points[ii].y);
mt3 = abs(points[k].x - points[ii].x) + abs(points[k].y - points[ii].y);
// 3개의 대피소 까지 거리중 최소거리는
mt1 = (mt1 > mt2) ? mt2: mt1;
mt1 = (mt1 > mt3) ? mt3: mt1;
// 짧은 거리중 가장 긴 거리
if(mt1>mt) mt = mt1;
}
if(correct > mt ) correct = mt;
}
}
}
}
printf("%d\n",correct);
return 0;
}
========== 풀이 python ==========
N,K = map(int,input().split())
POINTS = []
correct = 200000
for i in range(N):
POINTS.append([int(x) for x in input().split()])
if K == 1:
for i in range(N): # 대피소가 설치될 위치
mt = 0
for j in range(N): # 거리를 측정할 집
if i==j : continue # 측정할 집과 대피소가 같은 경우
t = abs(POINTS[i][0]-POINTS[j][0]) + abs(POINTS[i][1]-POINTS[j][1])
if t > mt : mt = t # 대피소에서 가장 거리가 먼 집까지의 거리
if correct > mt : correct = mt # 가장 거리가 먼 집까지의 거리중 짧은 거리
elif K == 2:
for i in range(N): # 대피소가 설치될 위치 1
for j in range(N): # 대피소가 설치될 위치 2
if i==j : continue # 대피소가 중복설치된 경우 패스
mt = 0
for k in range(N):
if k==i or k==j : continue # 집과 대피소가 같은 위치인 경우 패스
t1 = abs(POINTS[i][0]-POINTS[k][0]) + abs(POINTS[i][1]-POINTS[k][1])
t2 = abs(POINTS[j][0]-POINTS[k][0]) + abs(POINTS[j][1]-POINTS[k][1])
t = min(t1,t2) # 대피소에서 가까운 대피소까지 거리 중 짧은거리
if t > mt : mt = t # 집에서 가장 가까운 대피소 까지 거리 중 가장 먼거리
if correct > mt : correct = mt # 가장 거리가 먼 집까지의 거리중 짧은 거리
elif K == 3:
for i in range(N): # 대피소가 설치될 위치 1
for j in range(N): # 대피소가 설치될 위치 2
if i == j : continue # 대피소가 중복설치된 경우 패스
for k in range(N): # 대피소가 설치될 위치 3
if i==k or j == k : continue # 대피소가 중복설치된 경우 패스
mt = 0
for ii in range(N):
if i == ii or j == ii or k == ii: continue # 집과 대피소가 같은 위치인 경우 패스
t1 = abs(POINTS[i][0]-POINTS[ii][0]) + abs(POINTS[i][1]-POINTS[ii][1])
t2 = abs(POINTS[j][0]-POINTS[ii][0]) + abs(POINTS[j][1]-POINTS[ii][1])
t3 = abs(POINTS[k][0]-POINTS[ii][0]) + abs(POINTS[k][1]-POINTS[ii][1])
t = min(t1,t2,t3) # 대피소에서 가까운 대피소까지 거리 중 짧은거리
if t > mt : mt = t # 집에서 가장 가까운 대피소 까지 거리 중 가장 먼거리
if correct > mt : correct = mt # 가장 거리가 먼 집까지의 거리중 짧은 거리
print(correct)