[백준] 1708: 볼록 껍질(Convex Hull) - JS (기하학적 알고리즘)

  목 차

• 문제
• 접근 방식
• 이 문제를 풀며 느낀점
• 문제 해결
• 풀이

 

---

  문제

 

 

 

 

  접근 방식

 

볼록 껍질(Convex Hull) 알고리즘을 풀기 위한 접근방법은 다양하지만, 나는 그라함 스캔 알고리즘(Graham's Scan Algorithm)을 사용하여 문제를 해결하였다.

 

 

 

  그라함 스캔(Graham's Scan)

 

• 기준점: y가 가장 작은 점, y가 가장 작은 점이 여러 개일 경우 x가 가장 작은 점을 기준점으로 정한다.
• 정렬: 점들을 반시계 방향으로 정렬한다. 쉽게 말해서 각도(혹은 기울기)를 기준으로 정렬을 한다.

 

정렬을 하게 되면 위와 같이 정렬이 될 것이다.

 

첫 번째 점과 두 번째 점을 스택(Stack)에 넣어준 채로 시작한다.(1번 점과 2번 점이 연결된 상태)

그리고 그다음 점이 반시계 방향인지 시계방향인지를 확인하면 된다. 

 

방향은CCW 알고리즘을 사용해서 확인하는데, 반시계 방향이면 양수를, 시계 방향이면 음수를, 같은 선 상에 있으면 0을 반환한다.

 

 

이제 순서대로 확인해 보자

 

 

1. 3번 점의 방향 확인 

 

3번은 반시계 방향이다. Stack.push(3) 

 

2. 4번 점의 방향 확인

 

4번 점도 반시계 방향이다. Stack.push(4)

 

3. 5번 점의 방향 확인 

 

5번 점도 반시계 방향이니 Stack에 추가해 준다. Stack.push(5)

 

4. 6번 점의 방향 확인

 

6번 점이 시계방향이다. 만약 반시계 방향이 발견된다면 B 에 위치한 점은 볼록 껍질에 해당이 되지 않는다.

그러므로 6번은 추가하지 않고 Stack.pop()을 하여 5를 빼준다.

 

5. 다시 한번 6번 점의 방향 확인

 

반시계 방향이다. 6을 스택에 추가해 준다. Stack.push(6)

 

6. 7번 점의 방향 확인

 

7번 점의 방향 역시 시계방향이다. Stack에 추가해 준다. Stack.push(7)

 

7. 8번 점의 방향 확인

 

8번 점의 ccw 값이 음수이다. 시계방향이므로 7번은 볼록 껍질에 해당되지 않는다. Stack.pop()

 

8. 다시 한 번 8번 점의 방향을 확인

 

반시계 방향이다. Stack.push(8) 이렇게 마지막 요소까지 확인하면 끝이다. 

 

볼록 껍질 완성

 

 

글들을 찾아보며 내가 이해가 되지 않아서 내가 이해할 수 있도록 단계별로 설명해 보았다.

 

그리고 코드를 제출하기 전에 아래 글에 대한 해당사항은 없는지 확인하자

 

[1708. 볼록 껍질] 자주 틀리는 이유와 반례

 

글 읽기 - [1708. 볼록 껍질] 자주 틀리는 이유와 반례

 

 

 

  이 문제를 풀며 느낀점

 

알고리즘 문제를 풀면 풀수록 언어에 대한 이해도가 깊어지는 것 같다. 이 문제를 풀며 나는 내가 퀵 정렬을 구현해야 하는 줄 알고 퀵 정렬을 공부하고 구현하였다. 근데 생각해 보니 배열 메서드 중에sort라는 메서드가 있었다. 그리고 sort 라는 메서드를 이해하기 위해서 여러 영상을 찾아보았고 글을 보았다. 그리고 이해하게 되었다.

 

이런 이해 하나하나가 모여 언어 자체에 대한 이해도를 깊게 만들어 줄 것이라고 생각한다.

 

비록 나는 지금 자바스크립트를 내려두고 자바를 공부하고 있지만, 알고리즘을 자바스크립트로 해왔기 때문에 자바는 다시 처음부터 해야 할 것 같다. 문제를 풀 수는 있어도 자바로 구현하려면 꽤나 애 먹을 것 같은 느낌이다. 

 

 

그리고 알고리즘을 제대로 모르고 내 머리대로 하려고 한다면 개고생이라는 것도 알았다. 당연하겠지만, 먼저 해당 알고리즘에 대해서 제대로 알고 설계를 하고 구현을 해야겠다는 생각이 빡 들었다. 알고리즘을 먼저 인터넷으로 찾아본다고 베끼는 것이라고 생각하지 말자.

 

 

 

  문제 해결

 

 

에러 발생:

  자바스크립트의 배열 메서드인 sort 메서드는 Number 타입의 반환을 기대한다. 하지만 내가 작성한 코드에서 각도가 같다면 거리가 가까운 점을 먼저 정렬하게 해야 하는데, 거리를 계산할 때 제곱 연산을 한다. 좌표 범위가 절댓값 40000인 것을 고려하면 32비트 정수로는 표현이 불가능한 범위이다. 그러므로 BigInt를 사용하여 연산을 해야 한다. 그럼 자연스럽게 BigInt 타입의 값을 반환하게 되는데, 이때 sort 메서드에서 에러가 난다. 

 

 

문제 해결:

  그럼 Number 타입을 반환해 주면 된다. 우리는 sort 메서드에게 1, 0 , -1 이렇게 세 가지 중 하나만 전달하면 된다.

그러니 비교는 BigInt로 해주고, 세 개의 값 중 하나만 반환하면 되는 것이다. 말로 하면 복잡하니 코드를 살펴보자.

arr.sort((p1, p2) => {
    const result = compare(p1, p2, base);
    if(result > 0n) return 1;
    if(result < 0n) return -1;
    if(result == 0n) return 0;
});

 

 

꽤나 직관적인 코드라고 생각한다.

 

 

 

  풀이

 

더 보기: 실패한 코드

// arr: 원본배열, left: 왼쪽 포인터, right: 오른쪽 포인터
function quickSort(arr, left = 0, right = arr.length - 1) {
	if(left <= right) {
		
    const pivotIndex = partition(arr, left, right);
    
		quickSort(arr, left, pivotIndex - 1)
    
		quickSort(arr, pivotIndex + 1, right)

  }
		
}


function partition(arr, left, right){

	// pivot: left(초기: 0), low: 왼쪽 포인터, high: 오른쪽 포인터
	const pivot = arr[left];
  let low = left + 1;
  let high = right;
  
	// low 와 high 가 교차할 때 까지 반복
  while(low <= high){
		
		// low 이동
    while(arr[low] < pivot) low++;
		// high 이동
    while(arr[high] > pivot) high--;

		// 두 포인터가 멈추었을 때 서로 교차하지 않았다면 서로변경
    if(low <= high){
      [arr[low], arr[high]] = [arr[high], arr[low]]
      low++;
      high--;
    }
  }

	// 두 포인터가 멈추었고 서로 교차하였을 때는 오른쪽 포인터와 pivot 을 변경
  [arr[left], arr[high]] = [arr[high], arr[left]]

	// 정렬된 pivot 은 high 의 자리에 있으므로 high 를 리턴
  return high
	
}

 

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');

const N = input[0];

const arr = new Array(N)

// 원본 2차원 배열 생성
for(let i = 1; i <= N; i++){
    arr[i - 1] = input[i].split(" ").map(BigInt)
}



function ccw(point1, point2, point3){
    return (point2[0] - point1[0]) * (point3[1] - point1[1]) - (point2[1] - point1[1]) * (point3[0] - point1[0]);
}

function distance(base, point){
    return (point[0] - base[0]) ** 2n + (point[1] - base[1]) ** 2n;
}

function compare(point2, point3, base){
    const angle = ccw(base, point3, point2);
    if(angle === BigInt(0)){
        return BigInt(distance(base, point2) - distance(base, point3));
    }
    return BigInt(angle);
}

let base = arr[1];
for(let i = 0; i < arr.length; i++){
    if(arr[i][1] < base[1] || arr[i][1] == base[1] && arr[i][0] < base[0]){
        base = arr[i];
    }
}


arr.sort((p1, p2) => {
    const result = compare(p1, p2, base);
    if(result > 0n) return 1;
    if(result < 0n) return -1;
    if(result == 0n) return 0;
});

const stack = [arr[0], arr[1]];

for(let i = 2; i < arr.length; i++){

    const direction = BigInt(ccw(stack[stack.length - 2], stack[stack.length - 1], arr[i]));

    if(direction > BigInt(0)) {
        stack.push(arr[i]);
    } else if(direction < BigInt(0)){
        stack.pop();
        i--;
    } else if(direction === BigInt(0)){
        stack.pop();
        stack.push(arr[i]);
    }

}


console.log(stack);