[백준] 17611 직각다각형 (C++)

작성일 In , Views: Disqus:

문제 링크 : https://www.acmicpc.net/problem/17611

풀이 및 구현

입력으로 주어진 단순직각다각형과 가장 많이 교차하는 수평선분 혹은 수직선분을 찾아야 하는 문제이다.

주어진 좌표의 범위가 $-500,000 ≤ x_i, y_i ≤ 500,000$ 이기 때문에
제일 먼저 든 생각은 x, y좌표를 전부 확인하면서 현재 몇 개가 겹쳐있는지 확인해도 될 것 같다는 생각이었다.

이를 바탕으로 조금만 더 최적화를 해보면 현재 몇 개의 선분이 겹쳐있는지 들고 있으면서 선분의 시작점, 끝점을 훑어보면 된다.

수평선, 수직선 각각의 경우에 대해 확인해야 하므로 들어온 입력으로 수평선과 수직선을 찾아내는 작업이 필요했다.

꼭짓점이 시계 방향으로 들어오므로 이전 점과 비교해서 x좌표가 같으면 수직선으로, y좌표가 같으면 수평선으로 넣어주었다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector<point> v(N); // typedef array<int, 2> point;
for (auto& [x, y] : v) cin >> x >> y;

vector<point> h, w;

// 이전 점과 현재 점을 비교하기 위해 1 ~ N까지 돌면서 
// 이때 N일 때는 인덱스를 벗어나므로 현재 점은 % N을 통해 보정해주었다.
for (int i = 1; i <= N; i++) { 
    if (v[i - 1][0] == v[i % N][0]) { // x좌표가 같으므로 수직선
        h.push_back({v[i - 1][1], v[i % N][1]});
    }
    else { // 그외에는 수평선이다.
        w.push_back({v[i - 1][0], v[i % N][0]});
    }
}

이후 함수에서 수직선, 수평선 각각에 대해 최대 교차 횟수를 구해주어야 한다.

가장 작은 좌표부터 시작해서 시작점과 만나면 +1, 끝점과 만나면 -1을 해주면서 이때의 최댓값을 구하면 최대 교차 횟수를 구할 수 있다.

이를 위해 각 선분의 모든 점을 {점, 선분 번호} 형식으로 분리하고 배열에 넣어 정렬했다.

배열을 순회하면서 선분 번호가 처음 나오면 +1, 다시 나오면 -1을 해주는 방식으로 구현을 할 수 있다.

이때 주의해야할 점이 몇가지 있는데 먼저 현재 구현대로는 선분의 값이 모두 시작점 < 끝점의 형식으로 되어 있지 않다는 것이다.

시계방향으로 점이 들어왔으므로 끝점 < 시작점인 경우가 있기 때문에 이를 확인해 먼저 swap을 해주어야 한다.

두번째로 선분이 시작하거나, 끝나는 곳이 겹칠 때 조심해야 한다. 시작하는 곳을 먼저 계산하게 되면 해당 지점에서는 변화가 없어야 하는데 하나 커진 값이 최댓값으로 들어갈 수 있기 때문이다.

따라서 각 점에서 계산할 때에는 선분이 끝나는 것을 먼저 계산해야 한다. 이를 위해 배열에 넣을 때 시작점은 {시작점, 선분 번호}, 끝점은 {끝점, -선분 번호} 형태로 넣어주었다.

array는 정렬할 때 인덱스 작은 값이 같으면 그 다음 인덱스를 기준으로 오름차순 정렬해주기 때문에 무조건 끝점을 먼저 계산할 수 있다.

1
2
3
4
5
6
7
8
vector<point> v(h.size() * 2);

for (int i = 0; i < h.size(); i++) {
    if (h[i][0] > h[i][1]) swap(h[i][0], h[i][1]); // 끝점 < 시작점이면 바꿔준다.
    v[i * 2] = {h[i][0], i + 1}; // 시작점은 양수, i가 0부터 시작하므로 선분번호를 1부터 넣어주었다.
    v[i * 2 + 1] = {h[i][1], -(i + 1)}; // 끝점은 음수
}
sort(v.begin(), v.end());

정렬을 완료했으면 v 벡터를 순회하면서 n이 음수일 때는 끝점이므로 교차 횟수를 -1, n이 양수일 때는 시작점이므로 교차 횟수를 +1하고, 최댓값을 계속해서 갱신하면 최대 교차 횟수를 구할 수 있다.

1
2
3
4
5
6
7
8
9
10
int cnt = 0, mx = 0;

for (auto [p, n] : v) {
    if (n < 0) { // 끝점이면 교차 횟수를 감소
        --cnt;
    }
    else { // 시작점이면 교차 횟수 증가 및 최댓값 갱신
        mx = max(mx, ++cnt);
    }
}

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <bits/stdc++.h>
using namespace std;

typedef array<int, 2> point;

int cal(vector<point>& h) {
    vector<point> v(h.size() * 2);

    for (int i = 0; i < h.size(); i++) {
        if (h[i][0] > h[i][1]) swap(h[i][0], h[i][1]);
        v[i * 2] = {h[i][0], i + 1};
        v[i * 2 + 1] = {h[i][1], -(i + 1)};
    }
    sort(v.begin(), v.end());

    int cnt = 0, mx = 0;

    for (auto [p, n] : v) {
        if (n < 0) {
            --cnt;
        }
        else {
            mx = max(mx, ++cnt);
        }
    }
    return mx;
}


int main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    int N; cin >> N;
    vector<point> v(N);
    for (auto& [x, y] : v) cin >> x >> y;

    vector<point> h, w;
    for (int i = 1; i <= N; i++) {
        if (v[i - 1][0] == v[i % N][0]) {
            h.push_back({v[i - 1][1], v[i % N][1]});
        }
        else {
            w.push_back({v[i - 1][0], v[i % N][0]});
        }
    }

    cout << max(cal(h), cal(w));
}

후기

img.png
처음 문제를 풀 때 시작점 > 끝점 이 경우를 고려하지 않아 틀렸다.
디버깅하면서 해당 경우를 찾아내어 swap 하는 걸로 바꿔주었다.

또한 imos 누적합으로 풀 수 있는데 imos의 개념만 알고 실제로 해당 알고리즘을 사용한 적이 없어 해당 방법은 잘 떠오르지 않았다.