풀이 과정 🔎
-
우선 조건을 만족하는 "K번 정점"에 대해 조금 더 이해해 보려고 했다. 문제에서는 이 정점이 루트가 되었을 때, 주어진 두 정점 A와 B의 "가장 가까운 공통 조상이 A이거나 B가 되지 않아야 한다"고 설명했다. 조금은 꼬아둔 설명이었던 것 같은데... 😌
-
다르게 이해하면 정점 K에서 정점 A로 가는 경로에 정점 B가 포함되거나, 그 반대의 경우(정점 B로 가는 경로에 정점 A가 포함)가 되어서는 안 된다, 즉 정점 K에서 두 정점으로 가는 경로는 겹치지 않아야 한다고 해석할 수 있었다.
-
여기까지 찾았을 때 그래프 탐색을 사용해야 할 것 같다고 생각했는데, 정점의 최대 범위가 300,000이므로 각 정점에 대해 이 정점이 조건을 만족하는지 판단하려고 하면 시간초과가 발생할 것 같았다. 따라서 해석한 조건을 반대로 접근해 봤다.
(1) 정점 A에서 정점 B로 가는 경로에 포함되는 정점
(2) (1)에 해당하는 정점으로부터 A와 B를 거치지 않고 도달할 수 있는 정점
- 이렇게 하면 답이 될 수 있는 모든 정점에서부터 시작하는 대신, 주어진 두 개의 정점으로부터 시작해서 탐색이 가능했다. 로직은 다음과 같이 구상했다.
(1)
A에서 시작하고,B를 찾아야 할 타겟 정점으로 둔다.
(2)A에 인접해 있는 각각의 정점들(a1,a2,a3...)에서 차례대로 BFS를 수행한다.
(3) 탐색 중A,B는 방문할 수 있는 정점에서 제외하고, 각 BFS 시행마다 방문한 정점의 개수를 센다.
(4) 탐색 중B를 발견할 경우, 해당 시행에서 방문한 정점의 개수가 정답이다.
정답 코드 ✅
// C++ 사용
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
// 각 정점에서 간선으로 이어지는 다른 정점들을 저장
vector <int> v[300001];
// DFS 탐색에서 특정 정점의 방문 여부를 저장
int visited[300001] = {0, };
int main() {
ios_base::sync_with_stdio(false);
int n, start, end, x, y;
// start = 주어진 두 정수 A, B 중 하나
// end = A, B 중 나머지 하나
cin>>n>>start>>end;
// 트리 입력
for(int i = 1; i < n; i++) {
cin>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
queue <int> q;
int count, cur, next;
bool correct = false;
visited[start] = 1;
// start에 인접한 각각의 정점으로부터 DFS 탐색 시작
for(int i = 0; i < v[start].size(); i++) {
q.push(v[start][i]);
visited[v[start][i]] = 1;
count = 0;
while(!q.empty()) {
cur = q.front();
q.pop();
// 탐색 중 end가 발견될 경우 현재 탐색에서 도달한 모든 정점은 조건 만족
if(cur == end) {
correct = true;
continue;
}
count++;
for(int j = 0; j < v[cur].size(); j++) {
next = v[cur][j];
if(visited[next] == 0) {
visited[next] = 1;
q.push(next);
}
}
}
if(correct) {
break;
}
}
// 조건을 만족한 탐색에서 방문한 정점의 개수
cout<<count<<'\n';
return 0;
}