원 이동하기 2
문제
좌표평면에 원의 중심이 x축 위에 있는 N개의 원이 존재한다.
N개의 원 중 임의의 두개의 원을 선택했을 때 내접, 외접 등 교점이 존재하지 않도록 존재한다.
하나의 원이 다른 원 안에 포함될 수는 있다.
하나의 원 내부에서 다른 원의 내부로 이동하려고 한다.
원 내부는 단 한 번만 방문 할 수 있으며 두 번 이상 방문을 할 수 없다.
문제 편의상 좌표평면을 원점이 (0, 0)이고 반지름이 무수히 큰 하나의 원이라고 가정하자.
그림은 직접 사이트 참조.
입력
첫 번째 줄에는 원의 개수 N이 주어진다.
두 번째 줄부터 N + 1번째 줄까지 원의 번호 k와 원의 중심 좌표 중 x좌표,
원의 반지름 r이 공백으로 구분되어 주어진다.
마지막 줄에는 두 원의 번호 A와 B가 공백으로 구분되어 주어진다. 주어지는 원의 번호 중 중복되는 수는 없다. 좌표평면의 번호는 0으로 가정한다.
출력
첫 번째 줄에는 방문한 원의 개수를 출력한다.
두 번째 줄에는 방문한 원의 번호를 순서대로 공백으로 구분하여 출력한다.
풀이
오랜만에 문제들을 풀고 있는데 아이디어가 재밌어서 가져왔다.
우선 문제 조건에서 주어지는 원의 개수가 20만개라 모든 비교를 통해 원의 상관관계를 구할 수는 없다.
하지만 X축 위에 원의 중심 좌표가 있고, 모든 원은 겹치지 않는다.
그러면 모든 원에 대해 왼쪽 끝 점과 오른쪽 끝 점은 다른 좌표를 가지게 되고
이는 괄호가 닫히는 것과 안 닫히는 것을 확인하는 스택 문제와 비슷한 형태가 된다.
그래서 원 A가 열린 상태에서 원 B가 열리면 A안에 B가 있다고 표현을 할 수 있다.
그렇게 그래프 관계로 표현한 뒤 DFS를 통해서 경로를 구할 수 있었다.
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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
int main()
{
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
using P=pair<ll,ll>;
long long mod = 1e9+7;
bool flag=0;
long long a, b, c, d;
long long n, m, t, k;
long long ans=0;
cin >> n;
struct cir{
int num;
int x;
int r;
};
vector<cir> v(n);
vector<vector<int>> graph(n+1);
vector<int> pos(3000000, 0); //150만을 더해
int pad=1500000;
for(int i=0;i<n;i++){
cin >> v[i].num >> v[i].x >> v[i].r;
pos[v[i].x-v[i].r+pad]=v[i].num;
pos[v[i].x+v[i].r+pad]=v[i].num;
}
stack<int> st;
st.push(0);
for(int i=0;i<3000000;i++){
if(pos[i]!=0){
if(st.top()!=pos[i]){ //다르면 새로 나온거
graph[st.top()].push_back(pos[i]);
graph[pos[i]].push_back(st.top());
//cout << "!!" << st.top() << ' ' << pos[i] << '\n';
st.push(pos[i]);
}
else{
st.pop();
}
}
}
cin >> a >> b;
vector<int> vis(n+1, 0);
vector<int> ansv;
function<void(int)> dfs=[&](int x){
ansv.push_back(x);
vis[x]=1;
if(x==b)flag=1;
if(flag)return; //찾았으면
for(int i=0;i<graph[x].size();i++){
if(!vis[graph[x][i]]){
dfs(graph[x][i]);
}
if(flag)return;
}
ansv.pop_back();
};
dfs(a);
cout<<ansv.size()<<'\n';
string sp="";
for(int i=0;i<ansv.size();i++){
cout<<sp<<ansv[i];
sp=' ';
}
return 0;
}