문제 이해 단계
https://www.acmicpc.net/problem/22948
문제는 앞서 풀었던 원 이동하기 1과 똑같다.
문제에 대한 자세한 설명은
원 이동하기 1에 대한 링크를 달아둘 테니 참고해 주길 바란다.
[C++] 백준 22946 - 원 이동하기 1
문제 이해 단계 문제 좌표평면에 N개의 원이 존재한다. N개의 원 중 임의의 두개의 원을 선택했을 때 내접, 외접 등 교점이 존재하지 않도록 존재한다. 하나의 원이 다른 원 안에 포함될 수는
howudong.tistory.com
이 문제에서 다른 점은 두 원을 지정해 준다는 점과
원 번호,x좌표,반지름이 입력으로 주어진다는 점이다.
그리고 출력으로 이동횟수와 더불어 이동한 원의 번호를 순서대로 출력해야 한다.
문제 접근 단계
원 이동하기 1 동일하게 반지름을 기준으로, 원을 오름차순 정렬한다는 생각을 했다.
큰 원은 작은 원 안에 속할 수 없고, 반지름의 크기가 A < B < C이다.
A가 B 내부에 있고 B가 C 내부에 있을 때
계산할 필요 없이 A는 C의 내부에 존재한다.
이 원리를 이용해 백준 예제 1의 그림을 노드 관계로 나타내보면 이런 그림이 나온다.
상위에 있는 노드는 하위에 있는 노드보다 더 큰 원이고
연결됐다는 의미는 한 원이 다른 원의 내부에 있다는 의미이다.
예를 들어 노드 2는 노드 1의 내부에 있고
노드 2와 노드 3은 서로 외부에 있다.
예제의 그림과 비교해서 보면 명확하게 이해가 될 것이다.
나는 Bottom-Up 방식을 사용하여 문제를 풀었다.
알고리즘 동작 방식은 다음과 같다.
1.
원들을 반지름의 크기를 기준으로 벡터에 오름차순 정렬하고
비교할 두 값 s과 e를 찾는다.
2.
s보다 큰 원들을 크기순대로 순서대로
내부, 외부 판단 탐색한다.
3.
탐색하다가 내부가 되는 원이 탐색되면
해당 원을 리스트에 넣고 s로 지정한다.
4.
2~3번 과정을 0번으로 갈 때까지 진행한다.
5.
이번에는 e로 2~3번 과정을 반복한다.
6.
이미 s에서 방문했던 노드에 도착했을 때
그 원을 리스트에 넣는다.
7.
그때의 원을 RPoint라고 저장해 둔다.
8.
s 리스트에 저장한 값은 RPoint를 만날 때까지 출력한다.
9.
e 리스트에 저장한 값은 역순으로 모두 출력한다.
말이 좀 많이 복잡했는데
위의 예시를 토대로 과정을 아래에 나타냈다.
먼저 시작하는 원 s에서 일어나는 BFS까지의 과정이다.
먼저 원들을 반지름의 크기에 따라 오름차순 정렬한 뒤,
s값을 기준으로 순차적으로 비교한다.
비교 결과가 내부에 있는 걸로 나올 때까지 비교하다가 나오면
그 값을 리스트에 넣고 그 값을 s로 바꾼 후 BFS를 돌린다.
편의상 BFS(1) 이런 식으로 나타내긴 했는데,
사실상 BFS(2)에서 계속해서 while문이 돌아가고 있다.
List에 2가 담겨있는 이유는 자기 자신이기 때문에 미리 넣어놨기 때문이다.
쭉 돌리다가 원 0(공백)에 도달하면 sList를 반환하고 종료한다.
이후 똑같은 BFS를 원 e를 기준으로 돌린다.
s에서 이미 방문한 원 0을 방문했기 때문에 리스트에 0을 넣고 eList를 반환했다.
과정 6에서는 아까 말했시피 RPoint를 기점으로 SList는 RPoint까지,
EList는 역순으로 모두 출력하였다.
EList 역순으로 출력하는 이유는 순서대로 출력하기 위해서인데,
도착지가 마지막 원 e가 되어야 하기 때문이다.
원리는 이러하다.
이제 자세한 것은 문제 구현 단계에서 다루겠다.
문제 구현 단계
int GetRelation(tuple<int, int, int> a, tuple<int, int, int> b) {
long double x1 = get<1>(a);
long double r1 = get<2>(a);
long double x2 = get<1>(b);
long double r2 = get<2>(b);
long double d = sqrt(pow((x2 - x1), 2));
if (r1 + r2 < d) return 0;
else if (d == 0 || abs(r1 - r2) > d) return 1;
}원 이동하기 1에서 쓰인 내부, 외부 판단하는 함수이다.
이건 똑같기 때문에 따로 설명할 것이 없긴 한데,
내부이면 1, 외부이면 0을 반환한다는 것만 기억하자.
vector<int> Bfs(int s1) {
queue<int> q;
vector<int> list;
int start = 0;
for (int i = 0; i < input.size(); i++) {
int n = get<0>(input[i]);
if (n == s1) start = i;
}
q.push(start);
list.push_back(get<0>(input[start]));
if (c[start]) return list;
c[start] = true;
while (!q.empty()) {
int x = q.front();
q.pop();
for (int i = x + 1; i < input.size(); i++) {
if (GetRelation(input[x], input[i])) {
if (!c[i]) {
c[i] = true;
q.push(i);
list.push_back(get<0>(input[i]));
}
else {
list.push_back(get<0>(input[i]));
rPoint = get<0>(input[i]);
return list;
}
break;
}
}
}
return list;
}핵심이 되는 BFS 함수이다.
매개변수로 기준이 되는 원의 번호를 받고 벡터를 반환한다.
오름차순 정렬한 입력값에서 매개변수의 위치를 찾고
그다음부터 하나씩 탐색하여 내부에 있는 원을 찾아 큐에 넣는 작업을 반복한다.
이 과정에서 리스트에 담는 과정도 반복하는데,
최종적으로 반환하는 것도 해당 리스트이다.
함수는 좀 길어 보이긴 하는데 사실상 뜯어보면 아까 설명했던 것처럼 별 것 없다.
유의해야 할 점은 내부에 있는 원이 이미 방문한 원일 때
그 원을 RPoint로 지정한다는 것이다.
vector<tuple<int, int, int>> input;
vector<int> map[200003];
bool c[200003] = { false, };
int s, e;
int rPoint = -1;
bool cmp(tuple<int, int, int> a, tuple<int, int, int> b) {
return get<2>(a) < get<2>(b);
}
int main() {
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(false);
int N;
vector<int> ans1, ans2;
vector<int> answer;
cin >> N;
tuple<int, int, int> empty = make_tuple(0, 0, 10000000);
for (int i = 1; i <= N; i++) {
int n, x, r;
cin >> n >> x >> r;
input.push_back(make_tuple(n, x, r));
}
cin >> s >> e;
input.push_back(empty);
sort(input.begin(), input.end(), cmp);
ans1 = Bfs(s);
ans2 = Bfs(e);
for (int i = 0; i < ans1.size(); i++) {
if (ans1[i] == rPoint) break;
answer.push_back(ans1[i]);
}
for (int i = ans2.size()-1; i >= 0; i--) {
answer.push_back(ans2[i]);
}
cout << answer.size() << "\n";
for (int i = 0; i < answer.size(); i++) {
cout << answer[i] << " ";
}main 함수 부분이다.
입력받은 원을 input 배열 안에 넣고 반지름에 따라 오름차순 정렬한다.
세 가지 값을 받아주기 위해 tuple을 사용하고,
특수한 정렬이기 때문에 cmp라고 따로 정렬값을 만들었다.
sList와 eList를 각각 따로 선언하고
두 개를 합치기 위한 answer라는 배열을 만들어서 각각 합쳐서 답을 구했다.
마지막으로 전체 코드를 올리고 문제를 끝내겠다.
#include <iostream>
#include <algorithm>
#include <vector>
#include <tuple>
#include <cmath>
#include <queue>
using namespace std;
vector<tuple<int, int, int>> input;
vector<int> map[200003];
bool c[200003] = { false, };
int s, e;
int rPoint = -1;
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> a, tuple<int, int, int> b) {
long double x1 = get<1>(a);
long double r1 = get<2>(a);
long double x2 = get<1>(b);
long double r2 = get<2>(b);
long double d = sqrt(pow((x2 - x1), 2));
if (r1 + r2 < d) return 0;
else if (d == 0 || abs(r1 - r2) > d) return 1;
}
vector<int> Bfs(int s1) {
queue<int> q;
vector<int> list;
int start = 0;
for (int i = 0; i < input.size(); i++) {
int n = get<0>(input[i]);
if (n == s1) start = i;
}
q.push(start);
list.push_back(get<0>(input[start]));
if (c[start]) return list;
c[start] = true;
while (!q.empty()) {
int x = q.front();
q.pop();
for (int i = x + 1; i < input.size(); i++) {
if (GetRelation(input[x], input[i])) {
if (!c[i]) {
c[i] = true;
q.push(i);
list.push_back(get<0>(input[i]));
}
else {
list.push_back(get<0>(input[i]));
rPoint = get<0>(input[i]);
return list;
}
break;
}
}
}
return list;
}
int main() {
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(false);
int N;
vector<int> ans1, ans2;
vector<int> answer;
cin >> N;
tuple<int, int, int> empty = make_tuple(0, 0, 10000000);
for (int i = 1; i <= N; i++) {
int n, x, r;
cin >> n >> x >> r;
input.push_back(make_tuple(n, x, r));
}
cin >> s >> e;
input.push_back(empty);
sort(input.begin(), input.end(), cmp);
ans1 = Bfs(s);
ans2 = Bfs(e);
for (int i = 0; i < ans1.size(); i++) {
if (ans1[i] == rPoint) break;
answer.push_back(ans1[i]);
}
for (int i = ans2.size()-1; i >= 0; i--) {
answer.push_back(ans2[i]);
}
cout << answer.size() << "\n";
for (int i = 0; i < answer.size(); i++) {
cout << answer[i] << " ";
}
}
시행착오
원 이동하기 1과 똑같은 문제인 줄 알고,
사실상 더 쉬운 줄 알았는데 접근을 다르게 해야 할 줄은 몰랐다.
원 이동하기 1은 DFS로 풀었고, 이 문제는 BFS로 풀었다.
게다가 이 문제에서도 헛짓거리를 좀 많이 해서
맞왜틀을 많이 외치고 코드를 처음부터 싹 다 갈아엎었다.
역시 세상에 쉬운 문제는 없나 보다. 자만 금지