[백준 / BOJ] 17403 가장 높고 넓은 성 (Graham scan)

문제

출처 : https://www.acmicpc.net/problem/17403

17403번: 가장 높고 넓은 성

2차원 평면에 n개의 표지판이 주어진다. 

이 표지판을 이용해서 다음 규칙을 만족하는 가장 높은 성을 짓는 문제이다.

- n층은 n-1층 위에 지어진다. 이때, 각 층은 최대한 넓어야하며, 가능한 한 적은 수의 표지판을 사용해야 한다.

---

풀이

컨벡스 헐 알고리즘으로 푸는 문제다.

 

논리는 간단한데,

1. 현재 선택되지않은 표지판을 이용해 가장 넓은 성을 만든다.

2. 남아있는 표지판을 이용해 가장 넓은 성을 만든다.

(이때, 1번에서 가장 넓은 성을 만들었으니, 남아있는 표지판은 모두 1번층 안에 속해있는것을 알 수 있다.)

위 1번과 2번을 남아있는 표지판의 갯수가 2개 이하일때 까지 반복하면된다.

 

위 논리를 구현하기 위해서, 정렬 함수를 3개 만들어 줘야한다.

1. 기본적인 (y,x)순 오름차순 정렬 함수

2. 가장작은 (y,x)표지판을 기준으로 모든 표지판을 반시계방향으로 정렬하는 함수

3. 이미 선택된 표지판을 중복 선택하지 않도록 마지막으로 옮기는 함수

 

이제, 위 3개의 정렬 함수를 이용해 다음과 같은 알고리즘을 만들 수 있다.

1. 기본적인 (y,x)순으로 정렬한다.

2. 정렬된 값에서 이미 선택된 표지판들을 맨 뒤로 옮긴다.

3. 선택되지 않은 표지판의 범위 (0, 선택되지 않은 표지판의 가장 뒤 idx)를 구한다.

4. 3번의 범위를 기준으로 모든 점을 반시계방향으로 정렬한다. 

5. 그레이엄 스캔 알고리즘을 수행한다.

 

위 과정을 남아있는 점이 2개 이하일때까지 반복해주면 된다.

 

정렬 함수 코드 조각을 첨부하는데, 이해가 어렵다면 아래 링크를 타고 들어가 전체 코드를 보도록 하자.

 

- 가장작은 (y,x)표지판을 기준으로 모든 표지판을 반시계방향으로 정렬하는 함수

struct{

    bool operator()(pair<pair<long long, long long>, int> pos1, pair<pair<long long, long long>, int> pos2){
        long long ccwResult = ccw(poses[0].first, pos1.first, pos2.first);
        if(ccwResult == 0) {
            long long ccwDir = ccw(poses[0].first, {poses[0].first.first + 1, poses[0].first.second}, pos2.first);
            if(ccwDir < 0) return pos1.first.second > pos2.first.second;
            if(ccwDir == 0) return pos1.first.first < pos2.first.first;
            return pos1.first.second < pos2.first.second;
        }
        return ccwResult > 0;
    }

} comparable;

- 이미 선택된 표지판을 중복 선택하지 않도록 마지막으로 옮기는 함수

struct{
    
    bool operator()(pair<pair<long long, long long>, int> pos1, pair<pair<long long, long long>, int> pos2){
        return floorCheck[pos1.second] < floorCheck[pos2.second];
    }

} comparableByFloor;

---

전체 소스코드

https://github.com/devxb/JJUNalgo/blob/master/17403%20가장%20높고%20넓은%20성/main.cpp

GitHub - devxb/JJUNalgo: 백준 알고리즘 소스코드🙃