1708 - 볼록 껍질
- 문제 보기: 1708 - 볼록 껍질
- 소요 시간: 54분 13초
- 풀이 언어:
java - 체감 난이도: 3️⃣~4️⃣
- 리뷰 횟수: ✅
풀이 키워드
스포주의
수학
풀이 코드
- 메모리: 27464 KB
- 시간: 460 ms
import java.util.*;
import java.io.*;
public class Main
{
static StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
static int n;
static long[][] dot;
static int ccw(long[] a, long[] b, long[] c) {
long ax = a[0];
long ay = a[1];
long bx = b[0];
long by = b[1];
long cx = c[0];
long cy = c[1];
// cross product
long v = (ax*by + bx*cy + cx*ay) - (ay*bx + by*cx + cy*ax);
if (v > 0) return 1; // counter-clockwise
else if (v < 0) return -1; // clockwise
else return 0; // in-line
}
static long dist(long[] a, long[] b) {
return (b[0]-a[0])*(b[0]-a[0]) + (b[1]-a[1])*(b[1]-a[1]);
}
public static void main(String[] args) throws IOException {
n = readInt();
dot = new long[n][2];
for (int i = 0; i < n; ++i) {
dot[i][0] = readInt(); // x
dot[i][1] = readInt(); // y
}
// graham scan
// 1. find minimum y(x if same) dot
int mndx = 0;
for (int i = 1; i < n; ++i) {
if (dot[i][1] < dot[mndx][1]) mndx = i;
else if (dot[i][1] == dot[mndx][1]) {
if (dot[i][0] < dot[mndx][0]) mndx = i;
}
}
// swap
long[] tmp = dot[0];
dot[0] = dot[mndx];
dot[mndx] = tmp;
// 2. sort by ccw from idx 1 to n-1
Arrays.sort(dot, 1, n, (a, b) -> {
int v = ccw(dot[0], a, b);
if (v != 0) return v*-1; // reverse sign
// sort by distance asc if in-line
long d1 = dist(dot[0], a);
long d2 = dist(dot[0], b);
return Long.compare(d1, d2);
});
// 3. scan
Deque<Integer> stack = new ArrayDeque<>();
stack.push(0);
stack.push(1);
for (int idx = 2; idx < n; ++idx) {
while (stack.size() >= 2) {
int bdx = stack.pop();
int adx = stack.peek();
if (ccw(dot[adx], dot[bdx], dot[idx]) > 0) {
stack.push(bdx);
break;
}
}
stack.push(idx);
}
System.out.println(stack.size());
}
static int readInt() throws IOException {
st.nextToken();
return (int)st.nval;
}
}
풀이 해설
기본적인 Convex Hull 알고리즘으로 풀이할 수 있는 기하학 문제이다.
📌 Graham Scan 알고리즘
정렬과 스캔이라는 2 step 로직을 통해 Convex Hull을 구하는 알고리즘이다.
시간복잡도는 이다.
한 줄 원리:
기준점에서 polar angle 순으로 나머지 점들을 정렬한 후, 그 순서대로 연결 선의 꺾임 방향이 일관되게 계속 좌회전인지 판단하여 필요 없는 점을 솎아내는 방식
1️⃣ 기준점 선정
을 정한다. 풀이 코드 상에선 dot[0]에 해당한다. 죽어도 클래스는 안 만들겠다는 똥고집
// 1. find minimum y(x if same) dot
int mndx = 0;
for (int i = 1; i < n; ++i) {
if (dot[i][1] < dot[mndx][1]) mndx = i;
else if (dot[i][1] == dot[mndx][1]) {
if (dot[i][0] < dot[mndx][0]) mndx = i;
}
}
으로 스캔하여 데카르트 좌표계 기준 가장 왼쪽 아래 구석에 짱박힌 점을 찾아낸다.
해당 점은 y 좌표값이 가장 작으면서, 만약 같은 y값의 다른 점이 존재할 시엔 가장 작은 x 좌표값을 가져야 한다.
long[] tmp = dot[0];
dot[0] = dot[mndx];
dot[mndx] = tmp;
짱박힌 점의 인덱스를 mndx라고 할 때, 인덱스 0과 swap하여 이후의 정렬을 준비한다.
2️⃣ 정렬
// 2. sort by ccw from idx 1 to n-1
Arrays.sort(dot, 1, n, (a, b) -> {
int v = ccw(dot[0], a, b);
if (v != 0) return v*-1; // reverse sign
// sort by distance asc if in-line
long d1 = dist(dot[0], a);
long d2 = dist(dot[0], b);
return Long.compare(d1, d2);
});
의 비용으로 정렬한다.
를 기준으로 두 점을 각각 비교해보았 을때, 반시계 방향 순으로 정렬한다.
formal 하게 표현하자면 polar angle이 작은 순으로 정렬하는 것이다.
만약 일직선 상에 나란히 놓여있어서 angle이 동일하다면, 둘 중 거리가 더 가까운 점 순으로 정렬한다.
3️⃣ 스캔
정렬 직후엔 사진과 같이 연결된 뭐라 표현할 수 없는 다각형 상태일 것이다.
이제 이 상태에서 두 인접한 선분들 간의 꺾인 관계를 판단하여, 반시계 방향으로 꺾이지 않는 경우는 솎아낸다.
Deque<Integer> stack = new ArrayDeque<>();
stack.push(0);
stack.push(1);
for (int idx = 2; idx < n; ++idx) {
while (stack.size() >= 2) {
int bdx = stack.pop();
int adx = stack.peek();
if (ccw(dot[adx], dot[bdx], dot[idx]) > 0) {
stack.push(bdx);
break;
}
}
stack.push(idx);
}
솎아낼 경우 이전 선분으로 되돌아가야 하므로 스택 구조를 활용한다.
물론 백트래킹도 생각해볼 수 있으나, 문제 상 점이 최대 40000개여서 스택이 정배이다.
일단 과 의 점 2개를 스택에 넣어놓고, , , 간의 벡터 외적을 구한다.
동일하게 정렬에서 사용했던 ccw 함수를 사용하면 되며, 외적이 양수일 경우 두 선분이 반시계 방향으로 꺾인 관계임을 의미한다.
반시계 방향으로 꺾인 관계라면 pop 했던 점을 다시 push하여 스택에 복구해준다.
만약 역방향으로 꺾이는 케이스가 나타난다면 복구하지 않는다.
그럼 while 문의 다음 iteration에서 그 날라간 점() 이전의 점()을 pop 하게 되고,
그 점과 현재 스캔 중인 점()을 다시 판단한다.
이후는 계속 같은 방식으로 점을 솎아내며 Convex Hull을 완성한다.
Covex Hull을 이루는 점의 개수는 스택에 들어있는 점의 개수와 같다.
메모
- 가성비 플래 문제
- 그레이엄 스캔보다 모노톤 체인 알고리즘이 더 효율적이라고 함 (시간복잡도는 동일)