[C++] 백준/BOJ - 22946 : 원 이동하기 1

 

---

문제 이해 단계

 

https://www.acmicpc.net/problem/22946

좌표평면 안에 N개의 원이 존재한다.

(1)N개의 원은 모두 겹치지 않는 상태거나,
(2)한 원이 다른 원이 내부에 속하거나
(3)두 원이 만나지 않는 경우
로만 존재한다.

이때, 하나의 원 내부에서 다른 원의 내부로 이동하는데, 한 원당 딱 한 번만 방문 가능하다.
좌표평면도 하나의 거대한 원으로 취급하여 방문 가능하다.

이런 조건일 때 한 원에서 다른 원으로 이동할 때,
얻을 수 있는 최대 이동 수를 얻는 문제이다.

 

 

---

문제 접근 단계

한 원을 기준으로 다른 원을 비교한다고 생각했을 때, 두 가지 상태로 밖에 존재하지 않는다.
내부에 있거나 외부에 있거나 둘 중 하나의 경우이다.

위의 문제 조건에서 한 원당 한 번씩밖에 방문을 못한다고 했다.

이 말을 문제에서 주어진 예시를 들어 본다면

eq7에서 eq3으로 이동하기 위해서는 eq2, eq1을 거쳐야 한다.

이를 상속관계 혹은 노드의 관계로 보면, eq7는 eq1과 eq2의 내부에 속하는 원이다.

이를 통해 알 수 있는 점은 한 원의 내부에 속한 원은 그 원의 자식 노드인 것을 알 수 있는 점이다.

여기서 0번 노드는 좌표평면을 의미하는 0번 원을 의미한다.

상속관계를 그림으로 나타내보면 이런 식으로 나타낼 수 있다.

가장 끝 노드인 7번에서 다른 끝노드인 4번 8번 0번까지 가면
총 4번 이동하므로 답은 4가 된다.

이 문제는 원들의 상속관계를 연결하고 DFS를 통해 깊이를 계산하여 답을 구하면 된다고 접근했다.

이렇게 하고 원들의 상속관계를 문제에서 주어진 위치관계 계산 힌트를 이용해 연결하려 했다.

근데 그럼 N이 최대 5000이고 두 원을 차례차례 비교해야 하는데, 
그럼 최악의 경우 (5000x5000 xDFS수행)이다.

근데 시간제한이 1초라 딱 봐도 시간초과가 뜰 것 같아서 다른 방법이 필요했다.

그래서 생각한 방법이 반지름의 길이에 따라 정렬한 후, 차례대로 비교하는 것이다.

상식적으로 반지름의 길이가 2인 원은 1인 원 내부에 속할 수 없다.

원 7은 가장 끝 노드이기 때문에 원 2에 속해지는 순간 더 이상 비교가 필요 없어진다.

이 원리를 이용해 모든 원들을 반지름의 크기에 따라 오름차순 정렬하여
반지름이 작은 원부터 차례대로 연결한다.

이렇게 하면 최악의 경우여도 N번만 수행하여도 모든 원을 연결할 수 있게 된다.

연결되는 로직은 다음과 같다.

1. 두 원의 위치관계 계산 결과가 내부인 경우
-> 두 노드를 연결하고 그 부모 노드를 자식노드로 하고,
그 부모 노드 다음 노드부터 또 차례대로 탐색

2. 외부인 경우
-> 패스하고 다음 노드와 비교

이렇게 모든 N까지 모든 원까지 탐색한 후 
DFS를 하여 최대 방문 횟수를 확인하여 답을 구한다.

말로 하다 보니 굉장히 복잡한데 코드를 보면서 자세히 설명하겠다.

 

 

---

문제 구현 단계

int GetRelation(tuple<int, int, int> k, tuple<int, int, int> l) {
	long double x1 = get<0>(k);
	long double y1 = get<1>(k);
	long double r1 = get<2>(k);
	long double x2 = get<0>(l);
	long double y2 = get<1>(l);
	long double r2 = get<2>(l);

	long double pow1 = (x2 - x1) * (x2 - x1);
	long double pow2 = (y2 - y1) * (y2 - y1);
	long double d = sqrt(pow1 + pow2);
	//외부에 있으면 0, 내부에 있으면 1을 반환
	if (r2 + r1 < d) return 0;
	else if (d == 0 || (abs(r2 - r1) > d)) return 1;
}

두 원의 위치관계를 계산하는 GetRelation 함수이다.
매개변수로 두 원의 정보를 받는다.

long double로 받는 이유는, 문제 조건에서 x, y가 -1000000~1000000이기 때문이다.

이는 제곱하는 과정에서 수가 엄청나게 커져,
오버플로우가 발생할 수 있음을 뜻해 크게 선언해 줬다.

계산 결과가 내부로 나오면 1, 외부로 나오면 0을 반환한다.

void Connect(int x) {
	int i = x + 1;
	bool endFlag = false;
	while (i < input.size()) {
		if (GetRelation(input[x], input[i])) {
			if (!map[i].empty()) endFlag = true;
			map[x].push_back(i);
			map[i].push_back(x);
			x = i;
		}
		if (endFlag) return;
		i++;
	}
}

원들을 연결하는 Connect 함수이다.

input은 입력받은 원을 반지름에 따라 오름차순 정렬해 둔 것의 리스트를 뜻한다.

인덱스 x과 x+1 ~ N까지 차례대로 GetRelation()을 진행한다.

여기서! map [i]. empty() 일 때 endFlag = true로 함수를 종료한다.

이 뜻은 비교하는 노드가 이미 연결돼 있을 경우
즉, 이미 사용 이력이 있을 경우를 의미한다.

이럴 때는 노드 x를 해당 노드를 연결하고 함수를 종료한다.

int Dfs(int x, int depth) {
	if (c[x]) return 0;
	c[x] = true;
	int cnt = depth;
	for (int i = 0; i < map[x].size(); i++) {
		int nx = map[x][i];
		depth = max(depth, Dfs(nx, cnt + 1));
	}
	c[x] = false;
	return depth;
}

최종적으로 DFS를 하여 이동 횟수를 구하는 함수이다.

일반적인 DFS와 같은데 다른 점은 DFS를 시작할 때 방문처리를 해준다.

이는 다른 노드에서도 방문을 하기 위해서 끝날 때 방문처리를 해제해 주는 것이다.

자세한 사항은 내가 예전에 풀어두었던 문제를 링크를 걸어 두겠다.

이 문제를 참고하면 이해가 쉽게 될 것이다.

https://howudong.tistory.com/31

[C++] 백준 13023 - ABCDE

bool cmp(tuple<int,int,int> a, tuple<int, int, int> b){
	return get<2>(a) < get<2>(b);
}

tuple<int, int, int> empty1 = make_tuple(0, 0, 10000000);
	input.push_back(empty1);
	cin >> N;
	for (int i = 1; i <= N; i++) {
		int x, y, r;
		cin >> x >> y >> r;
		input.push_back(make_tuple(x, y, r));
	}
	sort(input.begin(), input.end(), cmp);
	for (int i = 0; i < input.size(); i++) {
		if (map[i].empty()) Connect(i);
	}
	int answer = 0;
	for(int i = 0; i < input.size(); i++) answer = max(answer,Dfs(i,0));
	cout << answer;

main 함수 부분이다.

먼저 좌표평면을 임의의 함수로 만들어줬다.
어떤 수를 넣어도 내부에 있도록 하기 위해 가장 큰 수를 넣어줬다.

이후 cmp에 따라 sort를 실행하여 반지름에 따라 오름차순으로 정렬되게 하였다.

이후 가장 끝 노드부터 DFS를 실행하는데
중요한 것은 연결되지 않은 노드만 DFS를 실행하여 실행시간을 최소화한다는 것이다.

이후 가장 이동 횟수가 큰 answer가 답이 된다.

마지막으로 전체 코드를 올리고 풀이를 종료하겠다.

#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>
#include <cmath>

using namespace std;

vector<tuple<int, int, int>> input;
vector<int> map[5003];
bool c[5003] = { false };

int N;
bool cmp(tuple<int,int,int> a, tuple<int, int, int> b){
	return get<2>(a) < get<2>(b);
} 
int GetRelation(tuple<int, int, int> k, tuple<int, int, int> l) {
	long double x1 = get<0>(k);
	long double y1 = get<1>(k);
	long double r1 = get<2>(k);
	long double x2 = get<0>(l);
	long double y2 = get<1>(l);
	long double r2 = get<2>(l);

	long double pow1 = (x2 - x1) * (x2 - x1);
	long double pow2 = (y2 - y1) * (y2 - y1);
	long double d = sqrt(pow1 + pow2);
	//외부에 있으면 0, 내부에 있으면 1을 반환
	if (r2 + r1 < d) return 0;
	else if (d == 0 || (abs(r2 - r1) > d)) return 1;
}
void Connect(int x) {
	int i = x + 1;
	bool endFlag = false;
	while (i < input.size()) {
		if (GetRelation(input[x], input[i])) {
			if (!map[i].empty()) endFlag = true;
			map[x].push_back(i);
			map[i].push_back(x);
			x = i;
		}
		if (endFlag) return;
		i++;
	}
}
int Dfs(int x, int depth) {
	if (c[x]) return 0;
	c[x] = true;
	int cnt = depth;
	for (int i = 0; i < map[x].size(); i++) {
		int nx = map[x][i];
		depth = max(depth, Dfs(nx, cnt + 1));
	}
	c[x] = false;
	return depth;
}
int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);
	tuple<int, int, int> empty1 = make_tuple(0, 0, 10000000);
	input.push_back(empty1);
	cin >> N;
	for (int i = 1; i <= N; i++) {
		int x, y, r;
		cin >> x >> y >> r;
		input.push_back(make_tuple(x, y, r));
	}
	sort(input.begin(), input.end(), cmp);
	for (int i = 0; i < input.size(); i++) {
		if (map[i].empty()) Connect(i);
	}
	int answer = 0;
	for(int i = 0; i < input.size(); i++) answer = max(answer,Dfs(i,0));
	cout << answer;
}

 

 

---

시행착오

푸는데 3일 걸렸던 문제이다.

처음에는 반지름에 따라 내림차순 정렬하여 원을 연결하는 방식을 사용하였는데,
bad alloc, 메모리 초과, out of bound 등
여러 가지 오류 등을 맛보고 인터넷을 참고하려고 했다.

하지만 구글링을 해보아도 풀이가 된 문제가 없었다.

그러다 보니 오기가 생기더라.
내가 이 문제를 풀어서 블로그에 처음으로 기재해보고 싶었다.

다행히 다른 방법이 생각나서 문제를 풀 수 있었다.

한 문제를 오래 잡고 있는 것은 좋은 방법이 아니라고 배우긴 했는데, 오기가 생겨서 오래 풀어버렸다.
그래도 결국 풀어서 뿌듯하긴 하다.