[BOJ 10534]
문제 바로가기 : https://www.acmicpc.net/problem/10534
문제 설명은 위 링크에서 확인해주시길 바랍니다.
solution
review
스위핑 하면서 인접해있는 직사각형들을 집합으로 묶은 뒤에 각 집합별 넓이 중 최댓값을 출력하는 문제이다.
다만 스위핑을 가로로 1번, 세로로 1번 하면서 집합으로 묶어야 한다. 1번만에 모든 집합이 묶이지 않는다.
다른 분들의 풀이 설명도 참고해봤는데 대부분 이 방법에서 벗어나지 않았다. DICE님의 글에 자세하세 설명 돼있다.
집합으로 묶기 위해서 Union-Find를 이용하자.
원래는 순수하게 집합만 묶으려고 했는데 집합별 넓이를 모두 끌고오려면 묶을 때마다 값을 가져와야 한다.
처음에 집합으로 묶어놓고 마지막에 자식의 넓이를 부모에 모두 더하는 식으로 하려고 했지만 반례가 있었다.
실제로 그렇게 구현이 가능한지는 모르겠지만.. 그렇게 할 수 있는지 잘 모르겠다. 무튼 묶을 때마다 값을 가져왔다.
ll ret = 0;
//부모 찾기
int find(int a) {
if (uni[a] == a) return a;
return uni[a] = find(uni[a]);
}
//집합 묶어주기
void make_union(int a, int b) {
int pa = find(a), pb = find(b);
if (pa != pb) {
if (pa < pb) {
uni[pb] = pa;
//답에 영향을 주는 부분
if (!chk[pb]) {
area[pa] += area[pb];
ret = max(ret, area[pa]);
chk[pb] = true;
}
}
else {
uni[pa] = pb;
//답에 영향을 주는 부분
if (!chk[pa]) {
area[pb] += area[pa];
ret = max(ret, area[pb]);
chk[pa] = true;
}
}
}
}
스위핑을 위해서 직사각형에 있는 세로선 2개, 가로선 2개를 모아놓고 정렬해야 한다.
어느 방향으로 훑는지는 상관없다. 하지만 세로에서는 x, 가로에서는 y가 같을 때 일정한 방향으로 정렬해야 한다.
같은 시점에서 집합으로 묶어줄지 여부를 판단하기 때문이다.
나같은 경우 세로선은 아래부터, 가로선은 왼쪽부터 오도록 정렬해줬다.
struct height {
int x, y1, y2, num;
bool operator<(height& r) { return x == r.x ? y1 < r.y1 : x < r.x; }
};
struct row {
int y, x1, x2, num;
bool operator<(row& r) { return y == r.y ? x1 < r.x1 : y < r.y; }
};
vector<height> H; //세로선들
vector<row> R; //가로선들
...
sort(H.begin(), H.end());
sort(R.begin(), R.end());
이제 인접하는지 체크하면서 집합으로 묶어주면 된다!
이 문제는 직사각형끼리 모서리만 맞닿아도 인접했다고 기준을 정해줬기 때문에 주의해야 한다.
생각보다 인접 여부를 조건식으로 표현하는건 어렵지 않다.
가로의 경우 다음 그림과 같으며, 인접 조건은 R[i].x2 >= R[i+1].x1 이 된다.
(직사각형에서 왼쪽 x가 x1, 오른쪽 x가 x2, 아래쪽 y가 y1, 위쪽 y가 y2)
세로의 경우 다음 그림과 같으며, 인접 조건은 H[i].y2 >= H[i+1].y1 이 된다.
근데 위 2개 조건만 가지고 스위핑 하면서 집합을 만들면 다음 반례에서 걸린다.
3
0 0 10 10
1 10 1 1
3 10 1 1
ans : 102
빨간선을 R, 파란선을 B, 초록선을 G라고 하면 탐색을 R -> G -> B로 하게 된다.
R과 B를 비교하지 않는다. G, B만 비교하기 때문에 서로 같은 집합에 묶여야 하는데 묶이지 않는 문제가 발생한다.
그래서 조건에 맞아 같은 집합으로 묶게 됐을 때 각 선의 구간중 최소, 최대를 l, r로 뽑아서 각 선에 반영해줬다.
그럼 연속해서 탐색을 하게 돼도 문제가 생기지 않는다.
세로선은 x, 가로선은 y가 같을 때만 적용되기 때문에 다른 위치에서는 영향을 받지 않는다.
//옆으로 인접
for (int i = 0; i < n*2-1; i++) {
if (H[i].x == H[i+1].x) {
if (H[i].y2 >= H[i+1].y1){
//이 부분!
int l = min(H[i].y1, H[i + 1].y1);
int r = max(H[i].y2, H[i + 1].y2);
H[i].y1 = H[i + 1].y1 = l;
H[i].y2 = H[i + 1].y2 = r;
make_union(H[i].num, H[i+1].num);
}
}
}
//위아래로 인접할 때도 같은 방법으로 해주면 됩니다
금방 풀 줄 알았는데 반례에 부딪히면서 삽질하다가 하루가 지나서야 AC를 받았다.
이젠 보기만 해도 머리아프다. 망할 스위핑.
댓글남기기