[BOJ 5588] 별자리 찾기
- 문제풀이
문제
상근이는 밤하늘 사진에서 별자리를 찾고 있다. 사진에는 꼭 찾고 싶은 별자리와 같은 형태, 방향, 크기의 도형이 한 개가 포함되어 있다. 하지만, 상근이가 가지고 있는 사진 속에는 별자리를 구성하는 별 이외에 다른 별도 찍혀 있다.
왼쪽 그림은 상근이가 찾고자하는 별자리이다. 오른쪽 그림은 상근이가 가지고 있는 별자리 사진이고, 상근이가 찾은 별자리의 별은 동그라미가 쳐져 있다. 주어진 별자리의 별 좌표를 x방향으로 2, y방향으로 -3만큼 평행 이동하면 사진 속 위치가 된다.
꼭 찾고 싶은 별자리의 모양과, 사진에 찍힌 별의 위치가 주어졌을 때, 별자리 좌표를 사진 속 좌표로 변환하기 위해 변환해야 하는 양을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 찾고 싶은 별자리를 구성하는 별의 개수 m이 주어진다. 다음 m개 줄에는 별자리를 구성하는 별의 x좌표와 y좌표가 주어진다. 다음 줄에는 사진의 별의 개수 n이 주어진다. 다음 n개 줄에는 사진에 있는 별의 x좌표와 y좌표가 주어진다. (1 ≤ m ≤ 200, 1 ≤ n ≤ 1000) 별의 x 좌표와 y좌표는 0 이상, 1000000 이하이다.
출력
첫째 줄에 찾고 싶은 별자리 좌표를 얼마나 평행 이동하면 사진 속의 좌표가 되는지를 출력한다. 첫 번째 정수는 x 방향으로 평행 이동하는 양이고, 두 번째 정수는 y 방향으로 평행 이동하는 양이다.
제한
| 시간 제한 | 메모리 제한 |
|---|---|
| 1sec | 128MB |
풀이
찾으려는 별자리의 별 배치와 전체 밤하늘의 별들이 주어졌을 때, 별자리를 밤하늘에서 찾아내어 이동해야 하는 거리($x, y$)를 구하는 문제다.
별자리의 모든 별이 밤하늘에 포함되어 있어야 하므로, 별자리의 첫 번째 별이 밤하늘의 어느 한 별에 대응된다고 가정하고 나머지 별들도 동일한 간격으로 존재하는지 확인하는 방식을 취한다.
- 별자리의 별들을 $x$좌표, $y$좌표 순으로 정렬하고, 밤하늘의 별들도 동일하게 정렬한다
- 별자리의 첫 번째 별과 밤하늘의 각 별 사이의 거리 차이($tx, ty$)를 계산한다
- 계산된 ($tx, ty$)를 별자리의 나머지 별들에 더했을 때, 그 위치에 실제 밤하늘의 별이 존재하는지 이진 탐색으로 확인한다
- 모든 별이 존재함이 확인되면 해당 ($tx, ty$)가 정답이다
밤하늘의 별 개수가 $n$, 별자리의 별 개수가 $m$일 때 전체 시간 복잡도는 $O(n \times m \log n)$이 되며, $n, m \leq 1\,000$이므로 제한 시간 내에 충분히 해결 가능하다.
소스코드
Github Link : Source Code
참고 알고리즘 : 이진 탐색