백준 2162번
오늘 풀어본 문제는 백준의 2162번 문제1이다. 문제 풀이에 사용한 언어는 C++ 이다.
solved.ac 기준 CLASS
문제 정보
이 문제의 내용과 조건은 다음과 같다.
문제
$N$ 개의 선분들이 $2$ 차원 평면상에 주어져 있다. 선분은 양 끝점의 $x, y$ 좌표로 표현이 된다.
두 선분이 서로 만나는 경우에, 두 선분은 같은 그룹에 속한다고 정의하며, 그룹의 크기는 그 그룹에 속한 선분의 개수로 정의한다. 두 선분이 만난다는 것은 선분의 끝점을 스치듯이 만나는 경우도 포함하는 것으로 한다.
$N$ 개의 선분들이 주어졌을 때, 이 선분들은 총 몇 개의 그룹으로 되어 있을까? 또, 가장 크기가 큰 그룹에 속한 선분의 개수는 몇 개일까? 이 두 가지를 구하는 프로그램을 작성해 보자.
입력
첫째 줄에 $N$ $(1 \le N \le 3,000)$ 이 주어진다. 둘째 줄부터 $N+1$ 번째 줄에는 양 끝점의 좌표가 $x1, y1, x2, y2$ 의 순서로 주어진다. 각 좌표의 절댓값은 $5,000$ 을 넘지 않으며, 입력되는 좌표 사이에는 빈칸이 하나 있다.
출력
첫째 줄에 그룹의 수를, 둘째 줄에 가장 크기가 큰 그룹에 속한 선분의 개수를 출력한다.
풀이과정
1번째 시도
문제를 보고 선분교차 판정과 Union-Find 를 이용해야 한다는 것을 알 수 있었다. 각 선분끼리 교차하는지 확인하고, 교차한다면 인덱스끼리 합치는 것을 반복하여, 마지막에 그룹의 수와 가장 많은 선분을 가진 그룹에 담긴 선분의 개수를 출력해야하는 것이다.
선분교차 판정을 위해서 직접 만든 GeometricLine 클래스와 DisjointSet 클래스를 사용하였다. DisjointSet 클래스는 있는 그대로 활용하였고, GeometricLine 클래스는 기존의 클래스에 update 함수를 추가하였다. 각 클래스의 코드는 내 레포지토리2에서 확인할 수 있다.
코드는 다음과 같이 작성하였다. 제출할 때는 헤더파일의 내용을 main.cpp 에 붙여넣어 제출하였다.
geometric_line.hpp
#ifndef __GEOMETRIC_LINE_HPP__
#define __GEOMETRIC_LINE_HPP__
#include <utility>
template <typename T>
class GeometricLine {
private:
std::pair<T, T> start;
std::pair<T, T> end;
public:
GeometricLine() : start(std::make_pair(0, 0)), end(std::make_pair(0, 0)) {}
GeometricLine(const std::pair<T, T>& start, const std::pair<T, T>& end) : start(start), end(end) {
if (this->start > this->end) {
swap(this->end, this->start);
}
}
GeometricLine& operator=(const GeometricLine& other) {
this->start.first = other.start.first;
this->start.second = other.start.second;
this->end.first = other.end.first;
this->end.second = other.end.second;
return *this;
}
GeometricLine& update(const std::pair<T, T>& newStart, const std::pair<T, T>& newEnd) {
this->start = newStart;
this->end = newEnd;
return *this;
}
T getCCW(const std::pair<T, T>& target) const {
return (end.first - start.first) * (target.second - start.second) - (end.second - start.second) * (target.first - start.first);
}
bool cross(const GeometricLine& target) {
const T ourCCW = this->getCCW(target.start) * this->getCCW(target.end);
const T theirCCW = target.getCCW(this->start) * target.getCCW(this->end);
if (ourCCW == 0 && theirCCW == 0) {
if (this->start > target.end || target.start > this->end) {
return false;
}
else {
return true;
}
}
else {
return (ourCCW <= 0 && theirCCW <= 0);
}
}
const std::pair<T, T>& getStart(void) const {
return start;
}
const std::pair<T, T>& getEnd(void) const {
return end;
}
};
#endif // !__GEOMETRIC_LINE_HPP__
disjoint_set.hpp
#ifndef __DISJOINT_SET_HPP__
#define __DISJOINT_SET_HPP__
#include <vector>
class DisjointSet {
private:
std::vector<int> parent;
std::vector<int> rank;
public:
DisjointSet(int n) {
parent.resize(n);
rank.resize(n, 0);
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
int find(int u) {
if (u == parent[u]) {
return u;
}
else {
return parent[u] = find(parent[u]);
}
}
void merge(int u, int v) {
u = find(u);
v = find(v);
if (u != v) {
if (rank[u] > rank[v]) {
std::swap(u, v);
}
parent[u] = v;
if (rank[u] == rank[v]) {
rank[v]++;
}
}
}
};
#endif // !__DISJOINT_SET_HPP__
main.cpp
#include <bits/stdc++.h>
#include "geometric_line.hpp"
#include "disjoint_set.hpp"
using namespace std;
using ll = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int N;
cin >> N;
vector<GeometricLine<ll>> lines(N);
DisjointSet diset(N);
vector<int> lineCount(N, 0);
for (int i=0; i<N; i++) {
ll x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
lines[i].update({x1, y1}, {x2, y2});
}
for (int i=0; i<N; i++) {
GeometricLine<ll>& curr = lines[i];
for (int j=0; j<N; j++) {
GeometricLine<ll>& next = lines[j];
if (diset.find(i) != diset.find(j) && curr.cross(next)) {
diset.merge(i, j);
}
}
}
int groups = 0;
int maximum = INT_MIN;
for (int i=0; i<N; i++) {
int curr = diset.find(i);
if (lineCount[curr] == 0) {
groups++;
}
lineCount[curr]++;
maximum = max(maximum, lineCount[curr]);
}
cout << groups << "\n" << maximum;
return 0;
}
제출한 결과 ‘틀렸습니다’ 가 떴다.
2번째 시도
틀린 원인으로 알아낸 것은 새로 만든 update 함수에서 start 와 end 좌표의 위치를 정렬해주지 않은 것이었다.
선분 교차 판정 과정에서 CCW 값이 모두 $0$ 인 경우에는 두 선분이 나란히 위치하기 때문에 양끝점의 위치의 대소를 비교하여 교차판정을 진행하는데, 항상 시작점의 $x$ 좌표가 더 작도록 정렬되었음을 상정한다. 예전에 생성자를 만들 때는 제대로 이것을 넣어주었지만, 이번에 update 함수를 만들다가 이걸 깜빡 잊어버린 것이었다.
코드는 다음과 같이 수정하였다.
geometric_line.hpp (update function part)
GeometricLine& update(const std::pair<T, T>& newStart, const std::pair<T, T>& newEnd) {
this->start = newStart;
this->end = newEnd;
if (this->start > this->end) {
swap(this->end, this->start);
}
return *this;
}
그러자 모든 테스트 케이스를 통과하고 ‘맞았습니다’가 나오는 것을 확인할 수 있었다.
마무리
한 문제를 풀면서 두 개 이상의 직접 구현한 자료구조를 쓰는 일은 좀처럼 없는 편이라 이번 문제는 꽤 재미있었다. 미리 만들어두지 않았다면 엄청난 고생을 했겠지만, 제대로 저장을 해두고 만들 때 신경써서 만들어서 그런지 수월하게 풀 수 있었다. 나중에는 서너 개 넘게 사용하게 될 날이 올까?
오늘의 PS는 여기까지!
1: https://www.acmicpc.net/problem/2162
2: https://github.com/ChoiCube84/baekjoon-solutions/tree/main/C%2B%2B/2162