백준 9063번: 대지
주어진 여러 개의 점들을 모두 포함하는 가장 작은 직사각형의 넓이를 구하는 문제입니다. 직사각형의 변은 x축과 y축에 평행해야 합니다. 모든 점들의 x, y 좌표 중에서 최솟값과 최댓값을 찾는 것이 문제 해결의 핵심입니다.
✅ 문제 개요
| 항목 | 내용 |
|---|---|
| 문제 번호 | 9063번 - 대지 |
| 난이도 | 브론즈 3 |
| 핵심 알고리즘 | 구현, 기하학 |
✅ 문제 설명 요약
- 입력:
- 첫째 줄: 점의 개수
N(1 ≤ N ≤ 100,000) - 이후
N개의 줄: 각 점의x,y좌표 (-10,000 ≤ x, y ≤ 10,000)
- 첫째 줄: 점의 개수
- 출력: 주어진 점들을 모두 포함하는, 축에 평행한 직사각형의 최소 넓이
- 규칙:
- 직사각형의 모든 변은 x축 또는 y축에 평행해야 합니다.
- 점이 하나만 주어질 경우, 넓이는 0입니다.
✅ 풀이 전략
이 문제는 복잡한 기하학적 지식 없이, 주어진 모든 점을 둘러싸는 가장 작은 직사각형이 어떻게 결정되는지만 파악하면 쉽게 풀 수 있습니다.
1️⃣ 핵심 아이디어: 최소 경계 사각형
- 모든 점을 포함하면서 x, y축에 평행한 가장 작은 직사각형은, 모든 점들의 x좌표 최솟값/최댓값과 y좌표 최솟값/최댓값에 의해 결정됩니다.
- 즉, 직사각형의 네 경계선은
x = minX,x = maxX,y = minY,y = maxY가 됩니다.
2️⃣ 알고리즘 설계
- 필요한 값 찾기: 우리는 단 네 개의 값만 찾으면 됩니다:
minX,maxX,minY,maxY. - 초기값 설정: 이 네 변수를 초기화합니다. 가장 간단한 방법은 첫 번째로 입력받은 점의 좌표로 모두 초기화하는 것입니다.
minX = 첫 번째 x,maxX = 첫 번째 x,minY = 첫 번째 y,maxY = 첫 번째 y
- 최솟값/최댓값 갱신: 두 번째 점부터 마지막 점까지
for반복문으로 순회합니다.- 새로운 점
(x, y)를 입력받을 때마다, 기존의minX,maxX,minY,maxY와 비교하여 값을 갱신합니다. minX = Math.min(minX, x);maxX = Math.max(maxX, x);- (y좌표도 동일하게 갱신)
- 새로운 점
- 넓이 계산: 모든 점을 확인한 후,
너비 = (maxX - minX)와높이 = (maxY - minY)를 계산하여 둘을 곱하면 최종 넓이가 나옵니다.
3️⃣ 예외 처리: N=1
- 점이 하나만 주어지면 너비(
maxX - minX)와 높이(maxY - minY)가 모두 0이 됩니다. 따라서 넓이는 0입니다. 이 경우는 로직상 자연스럽게 처리되지만, 코드를 작성할 때 따로 분기하여 처리해 주면 더 명확합니다.
예시: Points (2, 4), (5, 2), (3, 8)
1. 초기값 (첫 점): minX=2, maxX=2, minY=4, maxY=4.
2. 두 번째 점 (5, 2):
- minX=min(2,5)=2, maxX=max(2,5)=5
- minY=min(4,2)=2, maxY=max(4,2)=4
- 현재 상태: minX=2, maxX=5, minY=2, maxY=4
3. 세 번째 점 (3, 8):
- minX=min(2,3)=2, maxX=max(5,3)=5
- minY=min(2,8)=2, maxY=max(4,8)=8
- 현재 상태: minX=2, maxX=5, minY=2, maxY=8
4. 최종 계산:
- 너비: maxX - minX = 5 - 2 = 3
- 높이: maxY - minY = 8 - 2 = 6
- 넓이: 3 * 6 = 18
✅ Java 코드 예제
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.io.IOException;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int N = Integer.parseInt(br.readLine());
// N=1인 경우, 넓이는 0
if (N <= 1) {
bw.write("0");
bw.flush();
bw.close();
br.close();
return;
}
// 1. 첫 번째 점의 좌표로 min/max 값 초기화
StringTokenizer st = new StringTokenizer(br.readLine());
int firstX = Integer.parseInt(st.nextToken());
int firstY = Integer.parseInt(st.nextToken());
int minX = firstX;
int maxX = firstX;
int minY = firstY;
int maxY = firstY;
// 2. 두 번째 점부터 순회하며 min/max 갱신
for (int i = 1; i < N; i++) {
st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
minX = Math.min(minX, x);
maxX = Math.max(maxX, x);
minY = Math.min(minY, y);
maxY = Math.max(maxY, y);
}
// 3. 넓이 계산 및 출력
int area = (maxX - minX) * (maxY - minY);
bw.write(String.valueOf(area));
bw.flush();
bw.close();
br.close();
}
}⚠️ 실전 주의사항
| 항목 | 설명 |
|---|---|
| 초기값 설정 | minX, maxX 등의 변수 초기화가 매우 중요합니다. 문제에서 주어진 좌표 범위 밖의 값(예: Integer.MAX_VALUE, MIN_VALUE)으로 설정하거나, 첫 번째 점의 좌표로 설정하는 것이 가장 안전하고 편리합니다. |
| N=1 예외 | 점이 하나일 때의 넓이는 0입니다. N=1일 경우 입력을 하나만 받고 바로 0을 출력하도록 코드를 분기하면 불필요한 연산을 줄일 수 있습니다. |
| 입력 성능 | N이 최대 100,000까지 가능하므로, Scanner보다는 BufferedReader와 StringTokenizer를 사용하는 것이 성능상 유리합니다. |
| 자료형 | 좌표와 N의 범위가 크지 않아 모든 계산은 int 자료형 내에서 충분히 처리 가능합니다. |
📝 마무리 요약
✔️ 모든 점을 포함하는 축에 평행한 최소 직사각형은 x좌표의 최댓값/최솟값과 y좌표의 최댓값/최솟값으로 결정됩니다.
✔️ 모든 점을 한 번씩만 순회하면서 이 네 가지 값(minX, maxX, minY, maxY)을 찾아냅니다.
✔️ 최종 넓이는 (maxX - minX) * (maxY - minY)로 간단히 계산할 수 있습니다.
✔️ 점이 하나일 때(N=1) 넓이는 0이라는 예외 케이스를 고려해야 합니다.
