중심 좌표가 (xc, yc)이고 높이가 h인 건물이 있다고 가정해 보겠습니다. 우리는 건물의 중심 좌표를 모르지만, x 좌표와 y 좌표 그리고 고도 값 a를 포함하는 n개의 정보를 제공받았습니다. 이때 좌표 (x, y)에서의 고도는 다음과 같이 정의됩니다.
altitude = max(h - |x - xc| - |y - yc|, 0)
즉, 주어진 정보들을 이용해 건물의 중심 좌표와 높이를 역으로 계산해야 합니다. 각 좌표 xi는 배열 x에, yi는 배열 y에, ai는 배열 a에 담겨 있습니다.
예를 들어 입력이 n = 3, x = {3, 3, 2}, y = {4, 2, 3}, a = {6, 6, 6}이라면 출력은 3 3 7이 됩니다. 즉, 중심 좌표는 (3, 3)이고 건물의 높이는 7입니다.
해결 접근 방식
이 문제는 브루트 포스(완전 탐색) 방식으로 해결할 수 있습니다. 가능한 모든 중심 후보 좌표 (xc, yc)를 순회하면서, 각 후보가 주어진 관측값들과 일치하는지 검증하는 것입니다.
핵심 아이디어는 다음과 같습니다.
- a[i] > 0인 지점에서는 h = a[i] + |x[i] - xc| + |y[i] - yc|가 성립해야 하며, 모든 양수 관측점에서 계산된 h 값이 서로 동일해야 합니다.
- a[i] = 0인 지점은 건물 밖에 있는 것이므로, 해당 지점까지의 맨해튼 거리 k가 반드시 h 이상이어야 합니다. 따라서 a[i] = 0인 지점들의 거리 최솟값 mh보다 h가 커서는 안 됩니다.
이 조건들을 만족하는 첫 번째 (xc, yc) 후보를 찾으면 그때의 h와 함께 출력하면 됩니다.
알고리즘 단계
check := true
for initialize xc := 0, when xc <= 100, update (increase xc by 1), do:
for initialize yc := 0, when yc <= 100, update (increase yc by 1), do:
check := true
mh := 2000000000
h := -1
for initialize i := 0, when i < n, update (increase i by 1), do:
k := |x[i] - xc| + |y[i] - yc|
if a[i] is same as 0, then:
mh := minimum of mh and k
else:
if h < 0, then:
h := a[i] + k
otherwise when h is not equal to a[i] + k, then:
check := false
Come out from the loop
if h > mh, then:
check := false
Ignore following part, skip to the next iteration
if check is non-zero, then:
Come out from the loop
print(xc, yc, h)C++ 구현 예제
아래 코드를 통해 실제 구현 방법을 더 자세히 살펴보겠습니다.
#include <bits/stdc++.h>
using namespace std;
void solve(int n, vector<int> x, vector<int> y, vector<int> a){
bool check = true;
int xc, yc, h;
for (xc = 0; xc <= 100; xc++) {
for (yc = 0; yc <= 100; yc++) {
check = true;
int k, mh = 2e9;
h = -1;
for(int i = 0; i < n; i++) {
k = abs(x[i] - xc) + abs(y[i] - yc);
if (a[i] == 0) {
mh = min(mh, k);
} else {
if (h < 0) {
h = a[i] + k;
} else if (h != a[i] + k) {
check = false;
break;
}
}
}
if (h > mh) {
check = false;
continue;
}
if (check) {
break;
}
}
if (check) {
break;
}
}
cout << xc << " " << yc << " " << h;
}
int main() {
int n = 3;
vector<int> x = {3, 3, 2}, y = {4, 2, 3}, a = {6, 6, 6};
solve(n, x, y, a);
return 0;
}입력
3, {3, 3, 2}, {4, 2, 3}, {6, 6, 6}출력
3 3 7
마무리
이 프로그램은 좌표 범위가 0~100으로 제한되어 있기 때문에 완전 탐색으로도 충분히 빠르게 동작합니다. 양수 고도 관측점에서 계산한 높이 값의 일관성과, 고도가 0인 지점과의 거리 제약 조건을 함께 검사함으로써 건물의 중심 좌표와 높이를 정확하게 도출할 수 있습니다.